Cod sursa(job #230506)

Utilizator vlad_DVlad Dumitriu vlad_D Data 14 decembrie 2008 02:41:44
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <iostream>
using namespace std;
#define nmax 30001
int tree[nmax];
int v[nmax];
int sol[nmax];
int n;
void update(int idx, int val) {
	while (idx <= n) {
		tree[idx] += val;
		idx += (idx & -idx);
	}
}
int gt(int idx) {
	int total = 0;
	while (idx) {
		total+= tree[idx];
		idx -= (idx & -idx);
	}
	return total;
}
int main() {
	ifstream fin("schi.in");
	ofstream fout("schi.out");
	
	fin >> n;
	
	int i, j;
	for (i = 1; i <= n; ++i) {fin >> v[i]; update(i, 1);}
	
	for (i = n; i >= 1; --i) {
		//find the v[i]th zero
		int left = 1, right = n;
		int sol2 = 0;
		while (left <= right) {
			int mid = (left + right) / 2;
			int val = gt(mid);
		        if (val >= v[i]) {
				if (val == v[i]) {if (sol2 == 0 || mid < sol2) sol2 = mid;}
				right = mid - 1;
			}
			else left = mid + 1;
		}


		sol[sol2] = i;
		update(sol2, -1);
	}	
	for (i = 1; i <= n; ++i) {
		fout << sol[i] << '\n';;
	}
	return 0;
}