Cod sursa(job #2116400)

Utilizator vladcainamisirVlad Cainamisir vladcainamisir Data 27 ianuarie 2018 16:26:03
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<cstdio>
const int N_MAX = 30000;
int sum [ 4 * N_MAX];
int v[ 1 + N_MAX ];
int ans[1 + N_MAX ];
void init(int nod , int st , int dr)
{
    int mid;
    if(st == dr){
        sum[nod] = 1;
    }
    else{
    mid = (st + dr) / 2;
    init(2 * nod , st , mid);
    init(2 * nod + 1 , mid + 1,  dr);
    sum[nod] = sum[2 * nod] + sum[2 * nod + 1];
    }
}
void update(int nod, int st , int dr , int index)
{
    int mid;
    if(st == dr)
        sum[nod] = 0;
    else
    {
        mid = (st + dr) / 2;
        if( index <= mid)
            update(2 * nod , st , mid , index);
        else
            update(2 * nod + 1 , mid + 1, dr , index);
        sum[nod] = sum[2 * nod] + sum[2 * nod + 1];
    }
}
int find_kth(int nod , int st , int dr , int index)
{
    int mid;
    if(st == dr)
        return st;
    mid = (st + dr ) / 2;
    if( index <= sum [ 2 * nod ])
        find_kth(2 * nod , st , mid , index);
    else
        find_kth(2 * nod + 1 , mid + 1 , dr , index - sum[2 * nod ]);
}
int main(){
    int n , i , poz;
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
    scanf("%d" , &n);
    for( i = 1; i <= n ; i ++)
    {
        scanf("%d", &v[i]);
    }
    init(1, 1, n);
    for( i = n ; i >= 1 ; i --)
    {
        poz = find_kth(1 , 1 , n ,v[i]);
        update( 1 , 1 , n , poz);
        ans[ poz ] = i;
    }
    for( i = 1; i <= n ; i ++)
    {
        printf("%d\n" , ans [ i ]);
    }
    return 0;
}