Cod sursa(job #1248217)

Utilizator rusu_raduRusu Radu rusu_radu Data 24 octombrie 2014 19:43:08
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <cstdio>
#include <assert.h>

#define Nmax 30005
using namespace std;

int n;
int AIB[Nmax];
int sol[Nmax];
int T[Nmax];
int zeros (int x) {
    return (x^(x-1))&x;
}

void update (int x, int val) {
    for (int i = x; i <= n; i += zeros(i)) {
        AIB[i] += val;
    }
}

int query (int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= zeros(i)) {
        sum += AIB[i];
    }
    return sum;
}

int binara (int val) {
	int st = 1, dr = n, p=n+1;
	while (st <= dr) {
		int mij = st + (dr-st)/2;
		int v = query(mij);
		if (query(mij) == val) {
			p = mij;
			dr = mij - 1;
		} else {
			if (v > val)
				dr = mij - 1;
			else
				st = mij + 1;
		}
	}
	return p;
}

int main() {
    assert(freopen ("schi.in", "r", stdin));
    assert(freopen ("schi.out", "w", stdout));

    scanf ("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", &T[i]);
		update (i, 1);
	}

    for (int i=n; i >= 1; i--) {
		int poz = binara (T[i]);
		sol[poz] = i;
		update (poz, -1);
    }
	for (int i=1; i<=n; i++)
		printf ("%d\n", sol[i]);
    return 0;
}