Cod sursa(job #35279)

Utilizator dominoMircea Pasoi domino Data 21 martie 2007 22:52:46
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>

#define MAX_N 30005
#define FIN "schi.in"
#define FOUT "schi.out"
#define LSB(x) (((x) & (x - 1l)) ^ (x))

int N, far A[MAX_N], T[MAX_N], far P[MAX_N];

void update(long n)
{
    for (; n <= N; n += LSB(n))
        T[n]++;
}

int query(long n)
{
    int t = n;

    for (n--; n > 0; n -= LSB(n))
        t -= T[n];
    return t;
}

int main(void)
{
    int i, j, k, a;
    long step;

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

    scanf("%d", &N);
    for (i = 0; i < N; i++)
        scanf("%d", A + i);

    for (step = 1; step < (long) N; step <<= 1);
    if (step > N) step >>= 1;

    for (i = N - 1; i >= 0; i--)
    {
        for (a = A[i], j = 1, k = step; k; k >>= 1)
            if (j + k <= N && query(j + k) <= a) j += k;
        P[j] = i + 1;
        update(j);
    }

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

    return 0;
}