Cod sursa(job #138416)

Utilizator damaDamaschin Mihai dama Data 18 februarie 2008 16:52:52
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>

const int nm = 30001;
int v[nm], sol[nm], arb[3 * nm], n;


int query(int nod, int st, int dr, int val);
void update(int nod, int st, int dr, int pos);
void init(int nod, int st, int dr);

int main()
{
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);

	int i, temp;

	scanf("%d", &n);
	for(i = 1; i <= n; ++i)
	{
		scanf("%d", &v[i]);
	}
	init(1, 1, n);
	/*
	for(i = 1; i <= n; ++i)
	{
		printf("%d %d\n", i, arb[i]);
	}
	*/
	for(i = n; i > 0; --i)
	{
		temp = query(1, 1, n, v[i]);
	//	printf("%d\n", temp);
		sol[temp] = i;
		update(1, 1, n, temp);
	}

	for(i = 1; i <= n; ++i)
	{
		printf("%d\n", sol[i]);
	}

	return 0;
}

void init(int nod, int st, int dr)
{
	if(st == dr)
	{
		arb[nod] = 1;
	}
	else
	{
		int fs = 2 * nod, fd = fs + 1, mid = (st + dr) / 2;
		init(fs, st, mid);
		init(fd, mid + 1, dr);
		arb[nod] = arb[fs] + arb[fd];
	}
}

int query(int nod, int st, int dr, int val)
{
	int fs = 2 * nod, fd = 2 * nod + 1, mid = (st + dr) / 2;
	if(st == dr)
	{
		return st;
	}
	if(arb[fs] >= val)
	{
		return query(fs, st, mid, val);
	}
	else
	{
		return query(fd, mid + 1, dr, val - arb[fs]);
	}
}

void update(int nod, int st, int dr, int pos)
{
	if(st == dr)
	{
		arb[nod] = 0;
	}
	else
	{
		int fs = 2 * nod, fd = fs + 1, mid = (st + dr) / 2;
		--arb[nod];
		if(pos <= mid)
		{
			update(fs, st, mid, pos);
		}
		else
		{
			update(fd, mid + 1, dr, pos);
		}
	}
}