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.