Cod sursa(job #934402)

Utilizator thebest001Neagu Rares Florian thebest001 Data 30 martie 2013 16:24:28
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>
int n,v[100001];
int t[100001];
int R[30001];
void genTree(int p,int st,int dr){
    if (st>=dr){
        t[p]=1;
        return;
    }
    int m=(st+dr)/2;
    genTree(2*p,st,m);
    genTree(2*p+1,m+1,dr);
    t[p]=t[2*p]+t[2*p+1];
}


int updateQuery(int Q,int p,int st,int dr){
    if (st==dr){
        t[p]--;
        return st;
    }
    int m=(st+dr)/2;
    int m1=t[2*p],m2=t[2*p+1];
    if (m1<Q){
        int result=updateQuery(Q-m1,2*p+1,m+1,dr);
        t[p]--;
        return result;
    } else {
        int result=updateQuery(Q,2*p,st,m);
        t[p]--;
        return result;
    }
}

int main(){

    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);


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

    genTree(1,1,n);

    int temp;

    for (int i=n;i!=0;i--){
        temp=v[i];
        R[updateQuery(temp,1,1,n)]=i;
    }

    for (int i=1;i<=n;i++)
        printf("%d\n",R[i]);

    return 0;

}