Cod sursa(job #1266632)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 18 noiembrie 2014 22:50:06
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>

using namespace std;

#define MAX 30001

int aib[MAX], pos_init[MAX], sol[MAX], n;

int lsb(int x) {
    return x&-x;
}

void update(int pos, int val) {
    for(; pos <= n; pos += lsb(pos)) {
        aib[pos] += val;
    }
}

int query(int pos) {
    int s = 0;
    for(; pos; pos -= lsb(pos)) {
        s += aib[pos];
    }
    return s;
}

int bs(int key) {
    int b = 1, e = n, m;
    while(b <= e) {
        m = (b+e) >> 1;
        if(key <= query(m)) {
            e = m - 1;
        }
        else {
            b = m + 1;
        }
    }
    return b;
}

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

    int i, poz;

    scanf("%d", &n);
    for(i = 1; i <= n; i++) {
        scanf("%d", &pos_init[i]);
        update(i ,1);
    }
    for(i = n; i; i--) {
        poz = bs(pos_init[i]);
        sol[poz] = i;
        update(poz, -1);
    }
    for(i = 1; i <= n; i++) {
        printf("%d\n", sol[i]);
    }
    return 0;
}