Cod sursa(job #637573)

Utilizator andra23Laura Draghici andra23 Data 20 noiembrie 2011 15:17:47
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<iostream>
#include<fstream>

using namespace std;

const int MAXN = 30010;
int place[MAXN], contestant[MAXN];
int tree[2*MAXN], leaf[2*MAXN];

void buildTree(int pos, int left, int right) {
	tree[pos] = right - left + 1;
	if (left < right) {
		int m = (left + right)/2;
		buildTree(pos*2, left, m);
		buildTree(pos*2+1, m+1, right);
	} else {
		leaf[pos] = left;
	}
}

int query(int pos, int val, int left, int right) {
	if (left == right) {
		tree[pos] = 0;
		return leaf[pos];
	}
	int result = 0;
	if (val <= tree[2*pos]) {
		result = query(2*pos, val, left, (left+right)/2);
		tree[pos]--;
	} else {
		result = query(2*pos+1, val-tree[2*pos], (left+right)/2+1, right);
		tree[pos]--;
	}
	return result;
}

int main() {
	ifstream f("schi.in");
	ofstream g("schi.out");
	int n;
	f >> n;
	for (int i = 1; i <= n; i++) {
		f >> place[i];
	}

	buildTree(1, 1, n);
	for (int i = n; i >= 1; i--) {
		int x = query(1, place[i], 1, n);
		contestant[x] = i;
	}
	
	for (int i = 1; i <= n; i++) {
		g << contestant[i] << '\n';
	}

	return 0;
}