Cod sursa(job #1559972)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 1 ianuarie 2016 02:55:10
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <cstdio>

const int DIM = 32768;
using namespace std;

int V[DIM], W[DIM], AIB[DIM], N, st, dr, mid;

void update_tree (int pos, int val) {
    for (pos = pos; pos <= N; pos += (pos & (-pos)))
        AIB[pos] += val;
    return;
}

int query_tree (int pos) { int val = 0;
    for (pos = pos; pos >= 1; pos -= (pos & (-pos)))
        val += AIB[pos];
    return val;
}

int main () {

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

    scanf ("%d", &N);

    for (int i = 1; i <= N; i ++) {
        scanf ("%d", &V[i]);
        update_tree (i, 1);
    }

    for (int i = N; i >= 1; i --) {
        st = 1, dr = N;

        while (st <= dr) {
            mid = st + (dr - st) / 2;

            if (query_tree (mid) < V[i])
                st = mid + 1;
            else
                dr = mid - 1;
        }

        W[st] = i;
        update_tree (st, -1);
    }

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

    return 0;
}