Cod sursa(job #149395)

Utilizator raduzerRadu Zernoveanu raduzer Data 5 martie 2008 17:56:32
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>

int n,vp,p,d[70000],poz,s,t,q;

void calc(int p, int a, int b)
{
     if (a==b)
     {
              s+=d[p];
              q=1;
              return;
     }
     int v=(a+b)/2;
     if (v<poz && q==0)
     {
               s+=d[p*2];
               calc(p*2+1,v+1,b);
     }
     else if (v>=poz && q==0) calc(p*2,a,v);
}

void search(int p, int a, int b)
{
     if (a==b)
     {
          poz=a;
          printf("%d ",a);
          d[p]=0;
          q=1;
          return;
     }
     int v=(a+b)/2;
     if (d[p*2]<t && q==0)
     {
          t-=d[p*2];
          search(p*2+1,v+1,b);
     }
     else if (d[p*2]>=t && q==0) search(p*2,a,v);
     d[p]=d[p*2]+d[p*2+1];
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    int i;
    vp=0;   
    while (vp<n) vp=1<<(++p);   
    for (i=vp; i<vp+n; ++i) d[i]=1;   
    for (i=p-1; i>=0; --i)   
        for (int j=1<<i; j<1<<(i+1); ++j) d[j]=d[j*2]+d[j*2+1];   
        
    poz=1;
    for (i=1; i<=n; ++i)
    {
        s=0;
        q=0;
        calc(1,1,vp);
        q=0;
        //printf("%d --\n",s);
        t=s+i;
        t%=d[1];
        if (t==0) t=d[1];
        search(1,1,vp);
    }
}