Cod sursa(job #736307)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 18 aprilie 2012 13:19:15
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<stdio.h>
#include<stdlib.h>

int i, n, x, v[30005], arb[100005], val, pos, xx, loc[30005], poz;

void update(int nod, int st, int dr)
{
	int m = (st + dr) / 2;
	if (st == dr)
	{
		arb[nod] = val;
	}
	else
	{
		if (pos <= m) update(2 * nod, st, m);
		if (pos > m) update(2 * nod + 1, m + 1, dr);

		arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
	}
}

void find(int nod, int st, int dr, int x)
{
	int m = (st + dr) / 2;
	if (arb[nod] == x && st == dr)
	{
		poz = st;
		arb[nod] = 0;
	}
	else
	{
		if (x <= arb[2 * nod]) find(2 * nod, st, m, x);
		else find(2 * nod + 1, m + 1, dr, x - arb[2 * nod]);

		arb[nod] = arb[2 * nod] + arb[2 * nod + 1];
	}
}


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

	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
	{
		scanf("%d",&v[i]);
		val = 1; pos = i;
		update(1,1,n);
	}

	for (i = n; i >= 1; i--)
	{
		xx = 0;		
		find(1,1,n,v[i]);
		loc[poz] = i;		
	}
	for (i = 1; i <= n; i++) printf("%d\n",loc[i]);
	return 0;
}