Cod sursa(job #1316301)

Utilizator ade_tomiEnache Adelina ade_tomi Data 13 ianuarie 2015 18:24:17
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>
#define max_n 30000
int v[4*max_n+4],val,poz,a,b,sol,n,k;
void update (int st, int dr, int nod)
{
    if(st==dr)
        v[nod]=val;
    else
    {
        int mid=(st+dr)/2;
        if(poz<=mid)
            update(st,mid,2*nod);
         else
             update(mid+1,dr,2*nod+1);
         v[nod]=v[2*nod]+v[2*nod+1];
    }


}
void query(int st, int dr, int nod)
{
    if(st>=a&&dr>=b)
        sol+=v[nod];
    else
    {
        int mid=(st+dr)/2;
        if(a<=mid)
            query(st,mid,2*nod);
         if(b>mid)
             query(mid+1,dr,2*nod+1);
    }
}
void  bs(int nod, int st, int dr,int caut)
{
    if(st==dr)
    {
        sol=st;
        return;
    }
    else
    {
        int mid=(st+dr)/2;
        if(v[2*nod]>=caut) bs(2*nod,st,mid,caut);
        else bs(nod*2+1,mid+1,dr,caut-v[2*nod]);
    }
}
int main()
{
    int i;
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        val=1;
        poz=i;
        update(1,n,1);

    }
  

    k=2;
    for(i=1;i<=n;i++)
    {
        
        k=(k+i-1)%v[1];
        if(k==0)
            k=v[1];
        sol=0;
        bs(1,1,n,k);
        printf("%d ",sol);
        poz=sol;
        val=0;
        update(1,n,1);

    }
    return 0;

}