Cod sursa(job #1540051)

Utilizator theep0Cruceru Radu theep0 Data 1 decembrie 2015 23:50:48
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <stdio.h>

#define MN 30001
#define FOR(i, a, b) for(i = (a); i <= (b); i++)
#define iFOR(j, a, b) for(j = (a); j >= (b); j--)

int s[MN], sol[MN];
int arb[4*MN];

void init(int i, int l, int r) {
    int m;
    if (l == r) {
        arb[i] = 1;
    } else {
        init(i * 2, l, (l+r)/2);
        init(i * 2 + 1, (l+r)/2+1, r);
        arb[i] = arb[i*2] + arb[i*2+1];
    }
}

void update(int i, int l, int r, int p) {
    int m;
    if (l == r) {
        arb[i] = 0;
    } else {
        m = (l + r) / 2;
        if (p <= m) {
            update(i * 2, l, m, p);
        } else {
            update(i * 2 + 1, m + 1, r, p);
        }
        arb[i] = arb[i * 2] + arb[i * 2 + 1];
    }
}

int query(int i, int l, int r, int v) {
    if (l == r) {
        return l;
    }
    else {
        if (arb[i*2] >= v) {
            return query(i*2, l, (l+r)/2, v);
        } else {
            return query(i*2+1, (l+r)/2+1, r, v-arb[i*2]);
        }
    }
}

int main() {
    int i, n, j;
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    scanf("%d", &n);
    FOR(i, 1, n) scanf("%d", s+i);
    init(1, 1, n);
    iFOR(i, n, 1) {
        j = query(1, 1, n, s[i]);
        sol[j] = i;
        update(1, 1, n, j);
    }
    FOR(i, 1, n) printf("%d\n", sol[i]);
}