Cod sursa(job #315725)

Utilizator cristikIvan Cristian cristik Data 16 mai 2009 21:49:02
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
#define bit(x) ((x^(x-1)&x))
int aib[30001],a[30001],sol[30001];
int n,i,k;
void update(int x,int val)
{
    int i;
    for(i=x; i<=n; i+=bit(i))
     aib[i]+=val;
}
int sum(int x)
{
    int i,rez=0;
    for(i=x; i>=1; i-=bit(i))
     rez+=aib[i];
    return rez;
}
int bs(int x)
{
    int i,step;
    for(step=1; step<n; step<<=1);
    for(i=n; step; step>>=1)
     if(i-step>=1 && x<=sum(i-step)) i-=step;
    return i;
}
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d",&n);
    for(i=1; i<=n; i++) scanf("%d",&a[i]);
    for(i=1; i<=n; i++) update(i,1);
    for(i=n; i>=1; i--)
    {
        k=bs(a[i]);
        sol[k]=i;
        update(k,-1);
    }
    for(i=1; i<=n; i++) printf("%d\n",sol[i]);
    return 0;
}