Cod sursa(job #961029)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 16:24:27
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <cstdio>
using namespace std;
 
inline int max(int a,int b)
{
    if(a>b)
        return a;
    return b;
}
 
inline int tata(const int nod)
{
    return nod/2;
}
inline int fiu1(const int nod)
{
    return nod<<1;
}
inline int fiu2(const int nod)
{
    return (nod<<1)+1;
}
 
struct sp
{
    int a=0,b=0;
    int val=0;
} v[500000];
 
void build(const int nod,const int a,const int b)
{
    v[nod].a=a;
    v[nod].b=b;
    v[nod].val=0;
    if(a<b)
    {
        int mij=(a+b)>>1;
        build(fiu1(nod),a,mij);
        build(fiu2(nod),mij+1,b);
    }
}
 
int x;
 
void get_x(int n)
{
    while(n)
    {
        x++;
        n=n>>1;
    }
}
 
inline void update(int nod)
{
    while(tata(nod)!=nod)
    {
        v[nod].val=v[fiu1(nod)].val+v[fiu2(nod)].val;
        nod=tata(nod);
    }
}
 
int poz=2;
int sol;
 
void query(const int nod,int val)
{
    if(nod>((1<<(x-1))-1))
    {
        sol=nod;
        return;
    }
    if(val>v[fiu1(nod)].val)
    {
        query(fiu2(nod),val-v[fiu1(nod)].val);
    }
    else
        query(fiu1(nod),val);
 
}
 
int n;
 
 
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    int np=n;
    while((n&(n-1))!=0)
        n++;
    get_x(n);
    build(1,1,n);
    for(int i=1;i<=np;i++)
    {
        v[(1<<(x-1))+i-1].val=1;
    }
    for(int i=(1<<(x-1))-1;i>=1;i--)
    {
        v[i].val=v[fiu1(i)].val+v[fiu2(i)].val;
    }
 
    /*for(int i=1,poz=1;i<=n;i=i*2)
    {
        for(int j=1;j<=i;j++,poz++)
        {
            printf("%d ",v[poz].val);
        }
        printf("\n");
    }*/
 
    for(int i=1;i<=np;i++)
    {
        poz+=i-1;
        poz=poz%v[1].val;
        if(poz==0)
            poz=v[1].val;
        sol=0;
        query(1,poz);
        v[sol].val=0;
        update(tata(sol));
        printf("%d ",sol-(1<<(x-1))+1);
    }
    return 0;
}