Cod sursa(job #785365)

Utilizator andunhillMacarescu Sebastian andunhill Data 8 septembrie 2012 17:47:48
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<fstream>
using namespace std;

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

int N;
int poz[30001];
int sta[30001];
int arb[32768];

void build(int node, int left, int right)
{	if(left == right)
	{	arb[node] = 1;
		return;
	}
	
	int mid = (left + right) / 2;
	build(2 * node, left, mid);
	build(2 * node + 1, mid + 1, right);
	
	arb[node] = arb[2 * node] + arb[2 * node + 1];
}

void update(int node, int left, int right, int pos)
{	if(left == right)
	{	arb[node] = 0;
		return;
	}
	
	int mid = (left + right) / 2;
	if(pos <= mid)
		update(2 * node, left, mid, pos);
	else update(2 * node + 1, mid + 1, right, pos);
	
	arb[node] = arb[2 * node] + arb[2 * node + 1];
}

int query(int node, int left, int right, int ith)
{	if(left == right)
		return left;
	
	int mid = (left + right) / 2;
	if(arb[2 * node] >= ith)
		return query(2 * node, left, mid, ith);
	else return query(2 * node + 1, mid + 1, right, ith - arb[2 * node]);
}

int main()
{	int i, j;
	
	f>>N;
	for(i = 1; i <= N; i++)
		f>>poz[i];
	
	build(1, 1, N);
	for(i = N; i >= 1; i--)
	{	j = query(1, 1, N, poz[i]);
		sta[j] = i;
		update(1, 1, N, j);
	}
	
	for(i = 1; i <= N; i++)
		g<<sta[i]<<'\n';
	
	f.close();
	g.close();
	return 0;
}