Cod sursa(job #996006)

Utilizator thewildnathNathan Wildenberg thewildnath Data 10 septembrie 2013 18:13:47
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>

int n,v[30002];

void update(int p,int nr)
{
    while(p<=n)
    {
        v[p]+=nr;
        p+=(p&-p);
    }
}

int query(int p)
{
    int s=0;
    while(p)
    {
        s+=v[p];
        p-=(p&-p);
    }
    return s;
}

int caut(int d,int nr)
{
    int s=0,p=0,i;
    while((1<<p)<=d)
        ++p;
    for(i=p-1;i>=1;--i)
        if(s+(1<<i)<d&&v[s+(1<<i)]<nr)
        {
            s+=1<<i;
            nr-=v[s];
        }
    return s+1;
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int i,p,a,b,c;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        update(i,1);
    printf("2 ");
    p=2;
    update(2,-1);
    for(i=2;i<=n;++i)
    {
        a=query(n);
        b=query(p-1);
        c=i%a;
        if(c<=a-b)
            p=caut(n,b+c);
        else
            p=caut(p,c-a+b);
        update(p,-1);
        printf("%d ",p);
    }
    printf("\n");
    return 0;
}