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.