jpol.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 61 行

{
PROB:jpol
LANG:PASCAL
}

program jpol;
const
  maxk=60;
var
  a:array[1..maxk*3]of word;
  no:array[1..maxk*3]of byte;
  b:array[1..maxk*2]of boolean;
  k,i,j,p,t,min,s1,s2:longint;
begin
  assign(input,'jpol.in');reset(input);
  assign(output,'jpol.out');rewrite(output);

  read(k);
  for i:=1 to k*3 do begin
    read(a[i]);no[i]:=i;
  end;

  for i:=k*3 downto k*2+1 do begin
    p:=i;
    for j:=1 to i-1 do
      if a[j]<a[p] then p:=j;
    t:=a[i];a[i]:=a[p];a[p]:=t;
    t:=no[i];no[i]:=no[p];no[p]:=t;
  end;

  for i:=k*2+1 to k*3 do
    writeln(no[i]);

  randomize;
  min:=k*500;
  repeat
    for i:=2 to k*2 do begin
      p:=random(i-1)+1;
      t:=a[i];a[i]:=a[p];a[p]:=t;
      t:=no[i];no[i]:=no[p];no[p]:=t;
    end;
    s1:=0;s2:=0;
    for i:=1 to k do
      if (s1>s2)=(a[i*2-1]>a[i*2]) then begin
        inc(s1,a[i*2]);inc(s2,a[i*2-1]);
        b[i*2-1]:=false;b[i*2]:=true;
      end
      else begin
        inc(s1,a[i*2-1]);inc(s2,a[i*2]);
        b[i*2-1]:=true;b[i*2]:=false;
      end;
  until (s1>min) and (s2>min);

  for i:=1 to k*2 do
    if b[i] then writeln(no[i]);
  for i:=1 to k*2 do
    if not b[i] then writeln(no[i]);

  close(input);close(output);
end.