Cod sursa(job #36207)

Utilizator gcosminGheorghe Cosmin gcosmin Data 23 martie 2007 10:32:41
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>

#define NMAX 30010

int N;

int a[NMAX];
int aib[NMAX];
int poz[NMAX];
int rez[NMAX];

inline int lsb(int x) { return (x & (x-1) ^ x); }

void update(int x, int sum)
{
	while (x <= N) {
		aib[x] += sum;
		x += lsb(x);
	}
}
int query(int x)
{
	int rez = 0;

	while (x) {
		rez += aib[x];
		x -= lsb(x);
	}
	
return rez;
}

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

	scanf("%d", &N);

	for (i = 1; i <= N; i++) scanf("%d", &poz[i]);

	for (stepmax = 1; stepmax <= N; stepmax <<= 1);
	stepmax >>= 1;

	for (i = 1; i <= N; i++) update(i, 1);

	for (i = N; i >= 1; i--) {
		x = 0;
		for (step = stepmax; step; step >>= 1)
			if (x + step <= N && query(x + step) < poz[i])
				x += step;

		rez[x + 1] = i;
		update(x + 1, -1);
	}

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

fclose(stdin);
fclose(stdout);
return 0;
}