Cod sursa(job #826506)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 30 noiembrie 2012 20:25:31
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<cstdio>

#define Nmax 32768

int N, aib[Nmax], pinit[Nmax], pfinal[Nmax];

inline int lsb(int bit) {
    return (bit&(-bit));
}

void update(int val, int poz) {

    int i;

    for(i=poz; i<=N; i+=lsb(i))
        aib[i]+=val;
}

int query(int poz) {

    int rez, i;

    rez = 0;
    for(i=poz; i>=1; i-=lsb(i))
        rez+=aib[i];

    return rez;
}

int binary_search(int val) {

    int i, pas;

    for(pas = 1; pas < N; pas <<= 1);

    for(i = N; pas; pas >>= 1)
        if(i - pas >= 1)
            if(val <= query(i - pas))
                i -= pas;

    return i;

}

void read_data() {

    freopen("schi.in","r",stdin);
    int i;

    scanf("%d",&N);
    for(i=1; i<=N; ++i) {
        scanf("%d",&pinit[i]);
        update(1, i);
    }
}

void solve() {

    int i, pozfinal;

    for(i=N; i>=1; --i) {
        pozfinal = binary_search(pinit[i]);
        pfinal[pozfinal] = i;
        update(-1, pozfinal);
    }
}

void print_data() {

    freopen("schi.out","w",stdout);
    int i;

    for(i=1; i<=N; ++i)
        printf("%d\n",pfinal[i]);
}

int main() {

    read_data();
    solve();
    print_data();

    return 0;
}