Editorial for HAOI 5000
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include <iostream> #include <algorithm> #include <vector> #include <cstdio> using namespace std; int n,a[1000100]; vector <int> re; int calc(int l,int r) { l=(l+n)%n; r=(r+n)%n; return a[r]-a[l-1]+(l>r?a[n-1]:0); } int main() { int k,x; long long sumDist=0,best; cin >> n >> k; while (k--) { scanf("%d",&x); a[--x]++; sumDist+=min(x,n-x); } re.push_back(1); best=sumDist; for (int i=1;i<n;i++) a[i]+=a[i-1]; for (int i=1;i<n;i++) { sumDist+=calc(i-n/2,i-1)-calc(i,i+n/2-1); if (sumDist==best) re.push_back(i+1); if (sumDist<best) { best=sumDist; re.assign(1,i+1); } } cout << best << endl << re.size() << endl; for (int i=0;i<re.size();i++) printf("%d ",re[i]); return 0; }
Code mẫu của happyboy99x
#include<cstdio> #include<algorithm> using namespace std; typedef long long Long; const int N = 1e6 + 5; int c[N], n, k, nrst[N]; void enter() { scanf("%d%d",&n,&k); for(int i = 0; i < k; ++i) { int x; scanf("%d", &x); ++c[x-1]; } } void solve() { Long now = 0; int cnt = 0; for(int i = 0; i < n; ++i) now += (Long) c[i] * min(i, n-i); for(int i = n/2; i >= 0; --i) cnt += c[i]; Long nearest = now; int nNearest = 1; nrst[0] = 1; for(int l = 1, r = (n/2+1)%n; l < n; ++l, r = (r+1) % n) { now += k - 2*cnt + 2*c[l-1] - n % 2 * c[r]; cnt += c[r] - c[l-1]; if(now < nearest) nearest = now, nNearest = 0; if(now == nearest) nrst[nNearest++] = l + 1; } printf("%lld\n%d\n%d", nearest, nNearest, nrst[0]); for(int i = 1; i < nNearest; ++i) printf(" %d", nrst[i]); printf("\n"); } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
program HAOI5000; uses math; const maxn=1000006; fi=''; var a,kq,prev,next:array[1..maxn] of longint; inp:text; n,k,i,m,p,nl,nr,d,x:longint; l,r,res:int64; begin assign(inp,fi);reset(inp); readln(inp,n,k); for i:=1 to k do begin read(inp,x);inc(a[x]); end; for i:=1 to n-1 do next[i]:=i+1;next[n]:=1; for i:=2 to n do prev[i]:=i-1;prev[1]:=n; m:=n div 2+1; for i:=1 to m-1 do inc(r,a[i]*(i-1)); for i:=1 to m-1 do inc(nr,a[i]); for i:=m to n do inc(l,a[i]*(n-i+1)); for i:=m to n do inc(nl,a[i]); res:=l+r;d:=1;kq[1]:=1; for p:=2 to n do begin if a[prev[p]]>0 then begin dec(nr,a[prev[p]]); inc(nl,a[prev[p]]); end; if a[m]>0 then begin inc(nr,a[m]); dec(nl,a[m]); end; inc(l,nl);dec(r,nr); m:=next[m]; if l+r<res then begin res:=l+r;d:=1; kq[1]:=p; end else if l+r=res then begin inc(d);kq[d]:=p; end; end; writeln(res); writeln(d); for i:=1 to d do write(kq[i],' '); end.
Code mẫu của RR
{Cho K thi sinh thi may tinh ngoi o N vi tri quanh 1 vong tron. Cac thi sinh co the ngoi cung may (thi dong doi). Tim vi tri cua may giam thi sao cho tong khoang cach tu may giam thi den may cac thi sinh la nho nhat. Tim tat ca cac vi tri thoa man. Biet rang khoang cach tu may giam thi den may thi sinh duoc tinh theo cong thuc: d=min(abs(u-v),N-abs(u-v)) voi u,v la may giam thi va may thi sinh} {$R+,Q+,S+} PROGRAM HAOI5000; CONST fi=''; fo=''; maxn=1000000; maxk=100000; maxkq=maxn*maxk; VAR n,k:longint; a:array[1..maxn] of longint; sl,sr:array[1..maxn] of longint; l,r:array[1..maxn] of qword; Procedure ReadInput; Var f:text; i,x:longint; Begin Assign(f,fi); Reset(f); Readln(f,n,k); For i:=1 to k do begin Read(f,x); inc(a[x]); end; Close(f); End; Procedure Tinh1; Var i:longint; Begin For i:=2 to n do sl[i]:=sl[i-1]+a[i-1]; For i:=n-1 downto 1 do sr[i]:=sr[i+1]+a[i+1]; End; Procedure Tinh2; Var i:longint; k,k1:longint; Begin k:=n div 2; k1:=k+n mod 2; For i:=2 to k1 do l[i]:=l[i-1]+sl[i]; For i:=k1+1 to n do l[i]:=l[i-1]+sl[i]-sl[i-k]-sl[i-k1]; For i:=n-1 downto k1 do r[i]:=r[i+1]+sr[i]; For i:=k1-1 downto 1 do r[i]:=r[i+1]+sr[i]-sr[i+k1]-sr[i+k]; End; Procedure WriteOutput; Var f:text; i:longint; min:qword; sl:longint; Begin Assign(f,fo); Rewrite(f); min:=maxkq; For i:=1 to n do If l[i]+r[i]<min then min:=l[i]+r[i]; Writeln(f,min); sl:=0; For i:=1 to n do If l[i]+r[i]=min then inc(sl); Writeln(f,sl); For i:=1 to n do If l[i]+r[i]=min then Write(f,i,' '); Close(f); End; BEGIN ReadInput; Tinh1; Tinh2; WriteOutput; END.
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i) #define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i) #define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i) #define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) #define nl puts("") #define sp printf(" ") #define ok puts("ok") //#include <conio.h> template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} }; template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } const double PI = 2 * acos(0); const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"}; const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; //const int dr[] = {0, 0, -1, +1}; //const int dc[] = {-1, +1, 0, 0}; const int dr[] = {-2, -1, +1, +2, +2, +1, -1, -2}; const int dc[] = {+1, +2, +2, +1, -1, -2, -2, -1}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const double eps = 1e-9; const ll mod = 1000000000; typedef pair<int, int> II; using namespace std; #define maxn 2000005 #define maxe 100005 int a[maxn] = {0}, n, m, x, kq[maxn]; int main(){ // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); gi(n); gi(m); Rep(i, m){ gi(x); a[x]++; a[x + n]++; } ll l = 0, r = 0, suml = 0, sumr = 0; For(i, 1, (n + 1) / 2){ r += a[i]; sumr += a[i] * 1ll * (i - 1); } For(i, (n + 1) / 2 + 1, n){ l += a[i]; suml += a[i] * 1ll * (n + 1 - i); } ll res = suml + sumr; int size = 0; kq[size++] = 1; For(i, 2, n){ sumr -= (r - a[i - 1]); sumr += a[i + (n - 1) / 2] * 1ll * ((n - 1) / 2); suml += (l - a[i + (n - 1) / 2] + a[i - 1]); suml -= a[i + (n - 1) / 2] * 1ll * (n - 1 - (n - 1) / 2); r += a[i + (n - 1) / 2] - a[i - 1]; l -= a[i + (n - 1) / 2] - a[i - 1]; if(res > suml + sumr){ res = suml + sumr; size = 0; kq[size++] = i; } else if(res == suml + sumr) kq[size++] = i; } printf("%lld\n", res); printf("%d\n", size); Rep(i, size) printf("%d ", kq[i]); // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program HAOI5000; Const input = ''; output = ''; maxk = 120000; maxn = 1020000; Type PNode = ^TNode; TNode = record val: integer; org: boolean; link: PNode; end; Var n,k,ndiv: integer; st: array[1..maxn] of PNode; F: array[1..maxn] of int64; a,sign: array[1..maxk] of integer; free: array[1..maxn] of boolean; min: int64; Procedure push(m,v: integer; ch: boolean); Var P: PNode; Begin New(P); P^.val:= v; P^.org:= ch; P^.link:= st[m]; st[m]:= P; End; Procedure init; Var fi: text; i,tmp: integer; Begin Assign(fi, input); Reset(fi); Readln(fi, n, k); ndiv:= n div 2; For i:= 1 to k do Begin Read(fi, a[i]); If a[i] <= ndiv then sign[i]:= -1 else sign[i]:= 1; push(a[i],i, false); tmp:= a[i] + ndiv; If tmp > n then tmp:= tmp - n; push(tmp,i,true); End; Close(fi); End; Procedure solve; Var curr: int64; i,rate,tmp: integer; P: PNode; Begin curr:= 0; rate:= 0; For i:= 1 to k do Begin tmp:= abs(a[i] - 1); If tmp > ndiv then tmp:= n - tmp; curr:= curr + tmp; rate:= rate + sign[i]; End; min:= curr; F[1]:= curr; P:= st[1]; While P <> nil do Begin tmp:= P^.val; sign[tmp]:= -sign[tmp]; rate:= rate + 2 * sign[tmp]; P:= P^.link; End; For i:= 2 to n do Begin curr:= curr + rate; F[i]:= curr; If min > curr then min:= curr; P:= st[i]; While P <> nil do Begin tmp:= P^.val; sign[tmp]:= -sign[tmp]; rate:= rate + 2 * sign[tmp]; If odd(n) and P^.org then inc(curr); P:= P^.link; End; End; End; Procedure printresult; Var fo: text; i,num: integer; Begin Assign(fo, output); Rewrite(fo); Writeln(fo, min); Fillchar(free, sizeof(free), false); num:= 0; For i:= 1 to n do if F[i] = min then Begin inc(num); free[i]:= true; End; Writeln(fo, num); For i:= 1 to n do if free[i] then write(fo, i, ' '); Close(fo); End; Begin init; solve; printresult; End.
Comments