Cod sursa(job #43728)

Utilizator stef2nStefan Istrate stef2n Data 30 martie 2007 14:29:34
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>

#define infile "order.in"
#define outfile "order.out"
#define INTERV_MAX 65540

FILE *fin,*fout;
int N,V[INTERV_MAX];

void build(int n, int li, int ls)
  {
   if(li==ls)
     {
      V[n]=1;
      return;
     }
   build(2*n,li,(li+ls)/2);
   build(2*n+1,(li+ls)/2+1,ls);
   V[n]=V[2*n]+V[2*n+1];
  }

int query(int n, int li, int ls, int poz)
  {
   if(li==ls)
     return li+1;
   if(poz<=V[2*n])
     return query(2*n,li,(li+ls)/2,poz);
   else
     return query(2*n+1,(li+ls)/2+1,ls,poz-V[2*n]);
  }

void update(int n, int li, int ls, int poz)
  {
   if(li==ls)
     {
      V[n]=0;
      return;
     }
   if(poz<=V[2*n])
     update(2*n,li,(li+ls)/2,poz);
   else
     update(2*n+1,(li+ls)/2+1,ls,poz-V[2*n]);
   V[n]=V[2*n]+V[2*n+1];
  }

void solve()
  {
   int virtual_poz=2,poz,ramase=N;
   build(1,0,N-1);
   for(int i=1;i<=N;i++)
      {
       virtual_poz = (virtual_poz + i - 1) % ramase;
       if(virtual_poz==0)
         virtual_poz=ramase;
       poz = query(1,0,N-1,virtual_poz);
       fprintf(fout,"%d ",poz);
       update(1,0,N-1,virtual_poz);
       ramase--;
      }
  }


int main()
{return 0;
fin=fopen(infile,"r");
fscanf(fin,"%d",&N);
fclose(fin);

fout=fopen(outfile,"w");
solve();
fclose(fout);

return 0;
}