Cod sursa(job #36046)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 22 martie 2007 21:36:43
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>

#define MAXN 30005

int N;
short x[MAXN], y[MAXN], aib[MAXN];

inline int query( int poz )
{
	int rez = 0;
	for (; poz; poz -= (poz ^ (poz - 1)) & poz)
		rez += (int)aib[poz];
	return rez;
}

inline void update( int poz, int val )
{
	for (; poz <= N; poz += (poz ^ (poz - 1)) & poz)
		aib[poz] += val;
}

int main()
{
	freopen("schi.in", "rt", stdin);
	freopen("schi.out", "wt", stdout);

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%hd", x + i);
		update( i + 1, 1 );
	}

	for (int i = N - 1; i >= 0; i--)
	{
		int k, step;
		for (k = 0, step = 16384; step; step >>= 1)
			if (k + step <= N && query(k + step) < x[i])
				k += step;

		y[k + 1] = i;
		update( k + 1, -1 );
	}

	for (int i = 1; i <= N; i++)
		printf("%d\n", y[i] + 1);

	return 0;
}