Cod sursa(job #473019)

Utilizator blasterzMircea Dima blasterz Data 27 iulie 2010 17:43:58
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define N 30001
#define common int m = (l + r) >> 1, L = n << 1, R = L | 1
#define dim 8192

using namespace std;

char ax[dim];
int pz;

inline void cit (int &x)
{
	x = 0;
	while (ax[pz] < '0' || ax[pz] > '9')
		if (++pz == dim)
			fread (ax, 1, dim, stdin), pz = 0;

	while (ax[pz] >= '0' && ax[pz] <= '9')
	{
		x = x * 10 + ax[pz] - '0';
		if (++pz == dim)
			fread (ax, 1, dim, stdin), pz = 0;
	}
}



int H[3 * N];

int a[N];
int n;

void build (int n, int l, int r)
{
	if (l == r)
	{
		H[n] = 1;
		return;
	}

	common;

	build (L, l, m);
	build (R, m + 1, r);

	H[n] = H[L] + H[R];
}


void update (int n, int l, int r, int poz)
{
	if (l == r)
	{
		H[n] = 0;
		return ;
	}

	common;

	if (poz <= m)
		update (L, l, m, poz);
	else
		update (R, m + 1, r, poz);

	H[n] = H[L] + H[R];
}


int query (int n, int l, int r, int k)
{
	if (l == r) return l;

	common;

	int rez = 0;

	if (H[L] >= k)
		rez = query (L, l, m, k);
	else
		rez = query (R, m + 1, r, k - H[L]);

	return rez;
}

int sol[N];

void solve ()
{
	int i;
	build (1, 1, n);
	int poz;

	for (i = n; i; --i)
	{
		poz = query (1, 1, n, a[i]);
	
		sol[poz] = i;

		update (1, 1, n, poz);
	
	}

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


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

	cit (n);
	for (int i = 1; i <= n; ++i)
		cit (a[i]);

	solve ();

	return 0;
}