Cod sursa(job #216590)

Utilizator RobybrasovRobert Hangu Robybrasov Data 24 octombrie 2008 22:33:09
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
#define step (poz^(poz-1))&poz
#define N 30010

int A[N],V[N],rez[N],n,i,p;

void update(int poz,int val)
{
    while (poz<=n)
    {
        A[poz]+=val;
        poz+=step;
    }
}

int sum(int poz)
{
    int s=0;
    while (poz)
    {
        s+=A[poz];
        poz-=step;
    }
    return s;
}

int query(int val)
{
    int st,i;
    for (st=1; st<=n; st<<=1);
    for (i=0; st; st>>=1)
        if (i+st<=n && sum(i+st)<=val) i+=st;

    return i;
}

int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d\n",&n);
    for (i=1; i<=n; i++)
    {
        update(i,1);
        scanf("%d\n",&V[i]);
    }
    for (i=n; i; i--)
    {
        p=query(V[i]);
        rez[p]=i;
        update(p,-1);
    }
    for (i=1; i<=n; i++) printf("%d\n",rez[i]);

    return 0;
}