Cod sursa(job #473042)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 27 iulie 2010 19:23:01
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <fstream>
#define nmax 30005

using namespace std;

const char iname[] = "schi.in";
const char oname[] = "schi.out";

ifstream fin(iname);
ofstream fout(oname);

int N, A[nmax], Arb[3 * nmax], i, j, k, val, sol[nmax], rez;

inline void build(int nod, int left, int right)
{
	if(left == right)
	{
		Arb[nod] = 1;
		return;
	}

	int middle = (left + right) >> 1;
	build(2 * nod, left, middle);
	build(2 * nod + 1, middle + 1, right);
	Arb[nod] = Arb[nod * 2] + Arb[nod * 2 + 1];
}

inline void update(int nod, int left, int right)
{
	if(left == right)
	{
		Arb[nod] = 0;
		return;
	}
	else
	{
		int middle = (left + right) >> 1;
		if(val <= middle)
			update(nod * 2, left, middle);
		else
			update(nod * 2 + 1, middle + 1, right);
		Arb[nod] = Arb[nod * 2] + Arb[nod * 2 + 1];
	}

}

inline int query(int nod, int left, int right, int val)
{
	if(left == right) 
		return left;
	else
	{	
		
		int middle = (left + right) >> 1;
		if(Arb[nod * 2] >= val)
			return query(2 * nod, left, middle, val);
		else
			return query(2 * nod + 1, middle + 1, right, val - Arb[2 * nod]);
	}
}
	

int main()
{
	fin >> N;
	for(i = 1; i <= N; i ++)
		fin >> A[i];
	build(1, 1, N);
	for(i = N; i >= 1; i --)
	{	
		val = A[i];
		val = query(1, 1, N, val);
		sol[val] = i;
		update(1, 1, N);
	}
	for(i = 1; i <= N; i ++)
		fout << sol[i] << "\n";
	return 0;
}