Cod sursa(job #473043)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 27 iulie 2010 19:33:28
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 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 X[nmax], i, j, ArbInt[nmax * 3], k, sol[nmax], val, N;

void build(int nod, int left, int right)
{
	if(left == right)
	{
		ArbInt[nod] = 1;
		return;
	}
	else
	{
		int middle = (left + right) >> 1;
		build(nod * 2, left, middle);
		build(nod * 2 + 1, middle + 1, right);
		ArbInt[nod] = ArbInt[nod * 2] + ArbInt[nod * 2 + 1];
	}
}

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

void update(int nod, int left, int right)
{
	if(left == right)
	{
		ArbInt[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);
		ArbInt[nod] = ArbInt[nod * 2] + ArbInt[nod * 2 + 1];
	}
}
		

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