Cod sursa(job #227439)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 4 decembrie 2008 17:23:16
Problema Order Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.24 kb
var a:array[1..200000] of longint;
    f,g:Text;
    n,i,poz,x:longint;

procedure update(nod,st,dr:longint);
 var mij:longint;
 begin
  if st<dr then begin
   a[nod]:=dr-st+1;
   mij:=(st+dr) shr 1;
   nod:=nod shl 1;
   update(nod,st,mij);
   update(nod+1,mij+1,dr);
  end;
  if st=dr then
   a[nod]:=1;
 end;

function query(nod,st,dr,x:longint):longint;
 var mij:longint;
 begin
  if st<=dr then begin
   if st=dr then
    query:=st
   else begin
    mij:=(st+dr) shr 1;
    if a[nod shl 1]>=x then
     query:=query(nod shl 1,st,mij,x)
    else
     query:=query(nod shl 1+1,mij+1,dr,x-a[nod shl 1]);
   end;
  end;
 end;

procedure del(nod,st,dr,x:longint);
 var mij:longint;
 begin
  if st<=dr then begin
   dec(a[nod]);
   mij:=(st+dr) shr 1;
   if x>a[nod shl 1] then
    del(nod shl 1+1,mij+1,dr,x-a[nod shl 1])
   else
    del(nod shl 1,st,mij,x);
  end;
 end;

begin
 assign(f,'order.in'); reset(f);
 assign(g,'order.out'); rewrite(g);
 read(f,n);
 update(1,1,n);
 poz:=2;
 for i:=1 to n-1 do begin
  poz:=poz+i-1;
  poz:=poz mod (n-i+1);
  if poz=0 then
   poz:=n-i+1;
  x:=query(1,1,n,poz);
  write(g,x,' ');
  del(1,1,n,poz);
 end;
 writeln(g,query(1,1,n,1));
 close(f); close(g);
end.