Cod sursa(job #1385796)

Utilizator vladrochianVlad Rochian vladrochian Data 12 martie 2015 13:13:35
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
using namespace std;

const int kMaxN = 30005;

ifstream fin("schi.in");
ofstream fout("schi.out");

int N, pw2, pos[kMaxN], aib[kMaxN], standing[kMaxN];

void Erase(int pos) {
	for (int i = pos; i <= N; i += i & -i)
		--aib[i];
}

int Search(int val) {
	int pos = 0;
	for (int step = pw2; step; step >>= 1)
		if ((pos ^ step) <= N && aib[pos ^ step] < val) {
			pos ^= step;
			val -= aib[pos];
		}
	return pos + 1;
}

int main() {
	fin >> N;
	for (pw2 = 1; pw2 <= N; pw2 <<= 1);
	pw2 >>= 1;
	for (int i = 1; i <= N; ++i) {
		fin >> pos[i];
		aib[i] = i & -i;
	}
	for (int i = N; i; --i) {
		int crt = Search(pos[i]);
		standing[crt] = i;
		Erase(crt);
	}
	for (int i = 1; i <= N; ++i)
		fout << standing[i] << "\n";
	return 0;
}