Cod sursa(job #758340)

Utilizator toniobFMI - Barbalau Antonio toniob Data 15 iunie 2012 11:53:39
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
using namespace std;

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

int n, v[30030],aib[30003],rez[30003];

void update (int val, int poz) {
	while (poz <= n) {
		aib[poz] += val;
		poz += poz & (-poz);
	}
}
 
int suma (int poz) {
	int s = 0;
	while (poz) {
		s += aib[poz];
		poz &= poz - 1;
	}
	return s;
}

int bs (int x) {
	int step = 1<<17, i = 0;
	for ( ; step; step >>= 1) {
		if ( i + step <= n && suma (i + step) < x ) {
			i += step;
		}
	}
	update(-1, i+1);
	return i + 1;
}

int main () {
	in >> n;
	for (int i = 1; i <= n; ++i) {
		in >> v[i];
		update (1,i);
	}
	/*
	for(int i = 1; i<= n;++i)
		out << aib[i] << '\n';
	out << "\n";
	*/
	for (int i = n; i >= 1; --i) {
		rez [bs ( v [ i ] )] =  i  ;
	}
	for(int i = 1; i<= n;++i)
		out << rez[i] << '\n';

	return 0;
}