Cod sursa(job #1200969)

Utilizator timicsIoana Tamas timics Data 24 iunie 2014 00:43:28
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
int sol[30100],a[30100],t[30100],N;

int right(int x) {
    return ((x^(x-1))&x);
}

void add(int x, int y) {
    int curr = x;
    while(curr<=N) {
        t[curr]+=y;
        curr+=right(curr);
    }
}

int sum(int x) {
    int curr = x, ret = 0;
    while(curr) {
        ret += t[curr];
        curr -= right(curr);
    }
    return ret;
}

int caut(int x) {
    int st=1, dr=N, ret = -1;
    while(st<=dr) {
        int mij = (st+dr)/2;
        if(sum(mij)>=x) {
            ret=mij;
            dr=mij-1;
        } else {
            st = mij+1;
        }
    }
    return ret;
}

int main() {
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);
   // freopen("input.txt","r",stdin);
    scanf("%d",&N);
    for(int i=1;i<=N;++i) {
        scanf("%d",&a[i]);
        add(i,1);
    }
    for(int i=N;i>=1;--i) {
        int x = caut(a[i]);
        sol[x]=i;
        add(x,-1);
    }
    for(int i=1;i<=N;++i) {
        printf("%d\n",sol[i]);
    }
}