## 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.

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;
}

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);
for i:=1 to k do begin
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;
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;
st[m]:= P;
End;

Procedure init;
Var
fi: text;
i,tmp: integer;
Begin
Assign(fi, input);
Reset(fi);

ndiv:= n div 2;

For i:= 1 to k do
Begin
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];
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);
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.