Cod sursa(job #1823343)

Utilizator radu_uniculeu sunt radu radu_unicul Data 6 decembrie 2016 11:09:37
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<stdio.h>

int aib[30010],n,sol,logn;

void update(int x,int val)
{
    for(int i=x; i<=n; i+=i&(-i))
    {
        aib[i]+=val;
    }
}

int query(int x)
{
    int ret=0;

    for(int i=x; i>0; i-=i&(-i))
    {
        ret+=aib[i];
    }
    return ret;
}

int search(int nr)
{
    int poz = 0;
    for(int i=logn;i>=0;--i)
    {
        if((poz+(1<<i))<=n&&aib[poz+(1<<i)]<nr)
        {
            poz+=1<<i;
            nr-=aib[poz];
        }
    }
    return poz+1;
}

int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    int k=2, pos;
    for(int i=1; i<=n; i++) update(i,1);
    for(logn=1; (1<<logn)<=n; logn++);
    logn--;
    for(int j=2; j<=n; j++)
    {
        pos=search(k);
        update(pos,-1);
        printf("%d ",pos);
        k=(k-1+j)%(n-j+1);
        if(k==0) k=n-j+1;
    }
    pos=search(k);
    printf("%d",pos);
    return 0;
}