Cod sursa(job #381217)

Utilizator silvia_the_bestSilvia Pripoae silvia_the_best Data 9 ianuarie 2010 17:18:36
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>

#define FIN "schi.in"
#define FOUT "schi.out"

#define N 30010
#define M 65536

int A[M], V[N], S[N];

void update(int val, int p, int x, int l, int r)
{
    int m;

    m = (l + r) >> 1;

    if (l == r)
    {
        A[x] = val;

        return;
    }

    if (p <= m)
        update(val, p, 2 * x, l, m);
    else
        update(val, p, 2 * x + 1, m + 1, r);

    A[x] = A[2 * x] + A[2 * x + 1];
}

int query(int p, int x, int l, int r)
{
    int m;

    m = (l + r) >> 1;

    if (l == r)
        return l;

    if (A[2 * x] >= p)
        return query(p, 2 * x, l, m);
    else
        return query(p - A[2 * x], 2 * x + 1, m + 1, r);
}

int main()
{
    int i, n, p;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d", &n);

    for (i = 1; i <= n; ++ i)
    {
        scanf("%d", &V[i]);

        update(1, i, 1, 1, n);
    }

    for (i = n; i; -- i)
    {
        p = query(V[i], 1, 1, n);

        //printf("TEST : %d\n", p);

        S[p] = i;

        update(0, p, 1, 1, n);
    }

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