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.

Download