Cod sursa(job #753549)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 29 mai 2012 23:10:41
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>

using namespace std;

const int maxn = 30005;
int v[maxn], aib[maxn * 4], sol[maxn];

void build(int nod, int left, int right)
{
    int m;
    m = (left + right) / 2;
    if(left == right) {
        aib[nod] = 1;
        return;
    }
    build(2 * nod, left, m);
    build(2 * nod + 1, m + 1, right);
    aib[nod] = aib[2 * nod] + aib[2 * nod + 1];
}

int query(int nod, int left, int right, int x)
{
    int m;
    m = (left + right) / 2;
    //fprintf(stderr, "%d %d %d\n", left, right, aib[nod]);
    if(left == right)
        return left;
    if(x <= aib[nod * 2])
        return query(nod * 2, left, m, x);
    else
        return query(nod * 2 + 1, m + 1, right, x - aib[2 * nod]);
}

void update(int nod, int left, int right, int x, int y)
{
    int m;
    m = (left + right) / 2;
    if(left == x && left == right) {
        aib[nod] = y;
        return;
    }
    if(x <= m)
        update(2 * nod, left, m, x, y);
    else
        update(2 * nod + 1, m + 1, right, x, y);
    aib[nod] = aib[nod * 2] + aib[nod * 2 + 1];
}


int main()
{
    int n, i, q;
    freopen ("schi.in", "r", stdin);
    freopen ("schi.out", "w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; ++i)
        scanf("%d", &v[i]);
    build(1, 1, n);
    for(i = n; i > 0; --i) {
        q = query(1, 1, n, v[i]);
        //fprintf(stderr, "\n%d %d\n", q, i);
        sol[q] = i;
        update(1, 1, n, q, 0);
    }
    for(i = 1; i <= n; ++i)
        printf("%d\n", sol[i]);
    return 0;
}