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

const maxn=100010;
var n,m,re,num:longint;
    a,f,kq:array[0..maxn] of longint;

procedure rf;
var i:longint;
begin
     read(m,n);
     for i:=1 to n do
     begin
          read(a[i]);
          inc(f[(a[i]-1) mod m+1]);
     end;
end;

procedure calc;
var i,x,y:longint;
begin
     for i:=2 to n do
     begin
          x:=(a[i]-1) mod m+1;
          y:=(a[i-1]-1) mod m+1;
          if a[i]-a[i-1]>m then dec(f[y])
          else dec(f[x]);
     end;
     y:=(a[n]-1) mod m+1;
     dec(f[y]);
end;

procedure pr;
var i,s:longint;
begin
     re:=1;
     for i:=2 to n do
         if (a[i]-1) div m<>(a[i-1]-1) div m then inc(re);
     calc;
     s:=re; num:=1; kq[1]:=1;
     for i:=2 to m do
     begin
          s:=s+f[i-1];
          if s<=re then
          begin
               if s=re then inc(num)
               else
               begin
                    num:=1; re:=s;
               end;
               kq[num]:=i;
          end;
     end;
end;

procedure wf;
var i:longint;
begin
     writeln(re);
     for i:=1 to num do write(kq[i],' ');
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector<int> E[N];

map<int, int> cnt;
int cur;

int n, m;

void update(int x) {
    int v = x < 0 ? -1 : 1;
    x = abs(x);
    cnt[x] += v;
    if (v < 0 && cnt[x] == 0) --cur;
    if (v > 0 && cnt[x] == 1) ++cur;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x;
        int block = x / m + bool(x % m);
        update(block);
        int cut = x % m;
        if (cut > 0) {
            E[cut].push_back(-block);
            E[cut].push_back(block - 1);
        }
    }

    vector<int> ans;
    int best = cur;
    for (int i = 1; i <= m; ++i) {
        if (best == cur) {
            ans.push_back(i);
        } else if (best > cur) {
            best = cur;
            ans.clear();
            ans.push_back(i);
        }
        while (!E[i].empty()) {
            update(E[i].back());
            E[i].pop_back();
        }
    }
    cout << best << endl;
    for (int x : ans) cout << x << ' ';
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100001;
  snode=524288;
var
  f1,f2:text;
  d,x:array[1..MAXN] of longint;
  val:array[1..snode] of longint;
  m,n:longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i:longint;
begin
  read(f1,m,n); x[1]:=0;
  for i:=2 to n+1 do read(f1,x[i]);
end;
procedure update(u,v,k:longint);
  procedure visit(i,l,r:longint); inline;
  var
    mid:longint;
  begin
    if (v<l) or (r<u) then exit;
    if (u<=l) and (r<=v) then
      begin
        inc(val[i],k);
        exit;
      end;
    mid:=(l+r)>>1;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
  end;
begin
  visit(1,1,m);
end;
function get(u:longint):longint;
var
  kq:longint;
  procedure visit(i,l,r:longint);
  var
    mid:longint;
  begin
    if (u<l) or (r<u) then exit;
    if (l=r) then
      begin
        kq:=val[i];
        exit;
      end;
    if val[i]<>0 then
      begin
        val[i<<1]+=val[i];
        val[i<<1+1]+=val[i];
        val[i]:=0;
      end;
    mid:=(l+r)>>1;
    visit(i<<1,l,mid);
    visit(i<<1+1,mid+1,r);
  end;
begin
  visit(1,1,m);
  get:=kq;
end;
procedure solve;
var
  i,u,v:longint;
begin
  for i:=1 to n do
    if x[i+1]-x[i]>m then
      begin
        u:=x[i+1]-x[i]-m; v:=x[i] mod m+1;
        if u>m then begin update(1,m,u div m); u:=u mod m; end;
        if u=0 then continue;
        u:=u+v-1; if u>m then u:=u-m;
        if v<=u then update(v,u,1)
        else
          begin
            update(v,m,1);
            update(1,u,1);
          end;
      end;
end;
procedure ans;
var
  kq,i,u:longint;
begin
  for i:=1 to m do
    begin
      u:=(x[n+1]-i) div m+1-get(i);
      d[i]:=u;
    end;
  kq:=maxlongint;
  for i:=1 to m do kq:=min(kq,d[i]);
  writeln(f2,kq);
  for i:=1 to m do
    if d[i]=kq then write(f2,i,' ');
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>

#include <ctime>
#include <deque>
#include <bitset>
#include <cctype>
#include <utility>
#include <cassert>

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(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int 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))

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> 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> 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 = (int) 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;
}

typedef pair<int, int> II;

const ld PI = acos(-1.0);
const ld eps = 1e-9;

const int dr[] = {0, +1, 0, -1};
const int dc[] = {+1, 0, -1, 0};

const int inf = (int)1e9 + 5;
const ll linf = (ll)1e16 + 5;
const ll mod = (ll)1e9 + 7;

#define maxn 200005

int m, n, a[maxn];
vector<int> res;
vector<int> V[maxn];

int main(){
//  freopen("in.txt", "r", stdin);

    cin >> m >> n;
    For(i, 1, n){
        scanf("%d", &a[i]);
        V[(a[i] - 1) % m + 1].pb(i);
    }
    a[0] = -inf; a[n + 1] = inf + inf + maxn;
    int MIN, run = 0, u;
    For(i, 1, n){
        if((a[i] - 1) / m > (a[i - 1] - 1) / m) run++;
    }

    MIN = run; res.pb(1);
    For(i, 1, m - 1){
        Rep(j, sz(V[i])){
            u = V[i][j];
            if(a[u + 1] - a[u] > m) run--;
            if(a[u] - a[u - 1] > m) run++;
        }
        if(MIN > run){
            MIN = run;
            res.clear();
            res.pb(i + 1);
        }
        else if(MIN == run) res.pb(i + 1);
    }
    cout << MIN << endl;
    Rep(i, sz(res)) printf("%d%c", res[i], i == sz(res) - 1 ? '\n' : ' ');

    return 0;
}

Code mẫu của ll931110

#include <iostream>
#include <list>
#define MAXN 100001
#define MAXK 200001
using namespace std;

list<int> a[MAXN];
int num[MAXN],pos[MAXK],bpos[MAXN],val[MAXN],cnt[MAXK];
int n,m;
list<int>::iterator ll;

int main()
{
    int i,npos,res,t,s,minval;

    //freopen("nka1.in","r",stdin);
    //freopen("nka1.ou","w",stdout);

    npos = 0;
    pos[0] = -1;
    for (i = 1; i <= MAXK; i++) cnt[i] = 0;
    res = 0;

    scanf("%d%d", &m, &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &num[i]);
        t = num[i]/m;
        s = num[i] % m;
        if (s == 0) t--;

        if (t - 1 > pos[npos])
          {
              pos[++npos] = t - 1;
              pos[++npos] = t;
          }
        else if (t - 1 == pos[npos]) pos[++npos] = t;

        a[s].push_back(i);
        if (cnt[npos] == 0) ++res;
        ++cnt[npos];
        bpos[i] = npos;
    }

    val[1] = res;
    minval = res;
    for (i = 2; i <= m; i++)
    {
        ll = a[i - 1].begin();
        while (ll != a[i - 1].end())
        {
            t = *ll;

            --cnt[bpos[t]];
            if (cnt[bpos[t]] == 0) --res;

            ++cnt[bpos[t] - 1];
            if (cnt[bpos[t] - 1] == 1) ++res;

            ++ll;
        }
        val[i] = res;
        if (minval > val[i]) minval = val[i];
    }

    printf("%d\n", minval);
    for (i = 1; i <= m; i++)
      if (minval == val[i]) printf("%d ", i);
}

Code mẫu của skyvn97

#include<cstdio>
#include<map>
#include<vector>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
map<int,int> ii;
int a[MAX];
int res[MAX];
int cur[MAX];
vector<int> changein[MAX];
map<int,int> mp;
int n,m;
void init(void) {
    scanf("%d",&m);
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i]);
    FOR(i,1,n) changein[a[i]%m+1].push_back(i);
}
void add(int x,int u) {
    mp[x]+=u;
    if (mp[x]==0) mp.erase(x);  
}
void process(void) {
    FOR(i,1,n) {
        add((a[i]-1)/m,1);
        cur[i]=(a[i]-1)/m;
    }
    res[1]=mp.size();
    FOR(i,2,m) {
        FORE(it,changein[i]) {
            add(cur[*it],-1);
            cur[*it]--;
            add(cur[*it],1);
        }
        res[i]=mp.size();
    }
    //FOR(i,1,m) printf("%d ",res[i]); printf("\n");
    int best=n+7;
    FOR(i,1,m) if (best>res[i]) best=res[i];
    printf("%d\n",best);
    bool pre=false;
    FOR(i,1,m) if (res[i]==best) {
        if (pre) printf(" ");
        else pre=true;
        printf("%d",i);
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

    static int[] F, sum;

    static void add(int node, int left, int right, int x, int y) {
        if(x<=left && right<=y) {
            F[node] ++;
            return;
        }
        int mid = (left+right) / 2;
        if(x<=mid) add( 2*node, left, mid, x, y);
        if(mid<y) add( 2*node+1, mid+1, right, x, y);
    }

    static void dfs(int node, int left, int right, int cur) {
        cur += F[node];
        if(left==right) {
            sum[left] = cur;
            return;
        }
        int mid = (left+right) / 2;
        dfs( node * 2, left, mid, cur);
        dfs( node * 2 + 1, mid + 1, right, cur);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(kb.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(kb.readLine());
        int[] a = new int[n];
        F = new int[4*m];
        for(int i=0;i<n;++i) a[i] = Integer.parseInt(st.nextToken()) - 1;
        int res = 1;
        for(int i=0;i<n-1;++i) {
            int d = a[i+1] - a[i];
            if(d>=m) res++;
            else {
                int s = (a[i]+1) % m;
                int e = a[i+1] % m;
                //System.out.println( s + " " + e);
                if(s<=e) add( 1, 0, m-1, s, e);
                else {
                    add( 1, 0, m-1, s, m-1);
                    add( 1, 0, m-1, 0, e);
                }
            }
        }
        //System.out.println(res);
        sum = new int[m];
        dfs( 1, 0, m-1, 0);
        //for(int xx : sum) System.out.print(xx+ " ");
        //System.out.println();
        int min = 1000000;
        for(int xx : sum) min = Math.min( min, xx);
        System.out.println( res + min);
        for(int i=0;i<m;++i) if(sum[i]==min) System.out.print((i+1) +  " ");
        System.out.println();
    }
}