Cod sursa(job #1248347)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 24 octombrie 2014 22:46:57
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <vector>

using namespace std;

#define MOD1 32173
#define NMAX 30002


void read_int(int &value) {
	int sign = 1;
	char ch;
	value = 0;
	while(!isdigit(ch = getchar())) {
		(ch == '-') && (sign = -1);
	}
	do {
		value = value * 10 + (ch - '0');
	} while(isdigit(ch = getchar()));
	value *= sign;
}

int N;
vector <int> places, aib, answer;

void insert_aib(vector <int> &aib, int N, int pos, int val) {
	while (pos <= N) {
		aib[pos] += val;
		pos += pos & (pos ^ (pos - 1));
	}
}

int query_aib(vector<int> &aib, int pos) {
	int ans = 0;
	while (pos) {
		ans += aib[pos];
		pos -= pos & (pos ^ (pos - 1));
	}
	return ans;
}

int solve(int place) {
	int put = 1, rez = N + 1, aux;
	while (put <= N) {
		put <<= 1;
	}
	put >>= 1;
	while (put) {
		if (rez - put > 0) {
			aux = query_aib(aib, rez - put);
			if (aux >= place) {
				rez -= put;
			}
		}
		put >>= 1;
	}
	return rez;
}

int main () {
#ifndef INFOARENA
	freopen("input", "r", stdin);
#else
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);
#endif

	int i, where;

	read_int(N);
	places.resize(N);
	aib.resize(N + 1);
	answer.resize(N + 1);

	for(i = 0; i < N; ++i) {
		read_int(places[i]);
		insert_aib(aib, N, i + 1, 1);
	}

	for (i = N - 1; i >= 0; --i) {
		where = solve(places[i]);
		answer[where] = i + 1;
		insert_aib(aib, N, where, -1);
	}

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

	return 0;
}