Cod sursa(job #1001465)

Utilizator thewildnathNathan Wildenberg thewildnath Data 25 septembrie 2013 00:08:12
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>

int v[30002],n,a[30002],rez[30002];

inline int lsb(int x)
{
    return (x^(x&(x-1)));
}

void update(int p,int val)
{
    while(p<=n)
    {
        a[p]+=val;
        p+=lsb(p);
    }
}

inline int query(int p)
{
    int s=0;
    while(p>0)
    {
        s+=a[p];
        p-=lsb(p);
    }
    return s;
}

void caut(int i)
{
    int s,d,m,l;
    s=1;
    d=n;
    l=0;
    while(s<=d)
    {
        m=(s+d)/2;
        if(query(m)>=v[i])
        {
            d=m-1;
            l=m;
        }
        else
            s=m+1;
    }
    rez[l]=i;
    update(l,-1);
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    int i;
    scanf("%d",&n);

    for(i=1;i<=n;++i)
    {
        scanf("%d",&v[i]);
        update(i,1);
    }

    for(i=n;i>=1;--i)
        caut(i);

    for(i=1;i<=n;++i)
        printf("%d\n",rez[i]);
    return 0;
}