Cod sursa(job #237637)

Utilizator katakunaCazacu Alexandru katakuna Data 30 decembrie 2008 12:31:38
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>

int sol,poz,i,n,A[210111];

void update(int nod,int p,int u,int poz,int val){
int mij=(p+u)>>1;

  if(p == u){
  A[nod] = val;
  return ;
  }

  if(poz<=mij)  update(nod<<1,p,mij,poz,val);

  else          update((nod<<1)+1,mij+1,u,poz,val);

  A[nod] = A[nod<<1] + A[(nod<<1)+1] ;

}

int query(int nod,int p,int u,int poz){
int mij=(p+u)>>1;

  if(p == u)
  return p;

  if(poz <= A[nod<<1]) query(nod<<1,p,mij,poz);
  else                 query((nod<<1)+1,mij+1,u,poz - A[(nod<<1)]);

}

int main(){

FILE *f=fopen("order.in","r");
fscanf(f,"%d",&n);
fclose(f);

FILE *g=fopen("order.out","w");
  for(i=1;i<=n;i++)
  update(1,1,n,i,1);

poz=1;
  for(i=1;i<=n;i++){
  poz=(poz+i) % A[1];
   if(poz == 0) poz=A[1];
   
  sol=query(1,1,n,poz);
  fprintf(g,"%d ",sol);
  update(1,1,n,sol,0);

  poz--;
   if(poz == 0) poz=A[1];
  }
  
fclose(g);

return 0;
}