HAOI5000 - HAOI 5000
Tác giả: ll931110
Ngôn ngữ: Pascal
{$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.