Cod sursa(job #216785)

Utilizator RobybrasovRobert Hangu Robybrasov Data 25 octombrie 2008 21:21:28
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 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, int dr)
{
    if (st==dr) return st;
    else
    {
        int m=(st+dr)>>1;
        if (val<=sum(m)) return query(val,st,m);
        else        return query(val,m+1,dr);
    }
}

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],1,n);
        rez[p]=i;
        update(p,-1);
    }
    for (i=1; i<=n; i++) printf("%d\n",rez[i]);

    return 0;
}