Cod sursa(job #669418)

Utilizator informatician28Andrei Dinu informatician28 Data 26 ianuarie 2012 22:15:53
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<fstream> 
#define NMAX 30005

using namespace std; 
ifstream in("schi.in"); 
ofstream out("schi.out"); 

int N, Place[NMAX], Arb[3*NMAX], V[NMAX];

void Update(int nod, int st, int dr, int Pos, int Val)
{
	if(st == dr) 
	{
		Arb[nod] = Val; 
		return; 
	}
	else
	{
		int mid = (st + dr)/2; 
		if( Pos <= mid ) Update( 2*nod, st, mid, Pos, Val); 
		if( Pos > mid )  Update( 2*nod+1, mid+1, dr, Pos, Val);
		
		Arb[nod] = Arb[2*nod] + Arb[2*nod+1]; 
	}
}
int Query(int nod, int st, int dr, int Val) 
{
	if( st == dr ) 
	{
		return st; 
	}
	else 
	{
		int mid = (st + dr)/2; 
		if( Arb[2*nod] >= Val ) 
		{ 
			return Query(2*nod, st, mid, Val);
		}
		return Query(2*nod+1, mid+1, dr, Val-Arb[2*nod]); 
	}
}
int main() 
{
	int i;
	
	in >> N; 
	
	for(i = 1; i <= N; i++) 
		{
			in >> V[i]; 
			Update(1, 1, N, i, 1);
	}
	
	for(i = N; i >= 1; i--) 
	{
		int P = Query(1, 1, N, V[i]); 
		Place[P] = i; 
		Update(1, 1, N, P, 0);
		//V[i] = 0; 
	}
	
	for(i = 1; i <= N; i++) 
		out << Place[i] << '\n';
}