HAOI5000 - HAOI 5000

Tác giả: ladpro98

Ngôn ngữ: Pascal

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.

Download