Cod sursa(job #252404)

Utilizator FllorynMitu Florin Danut Flloryn Data 4 februarie 2009 13:27:51
Problema Order Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.78 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.