Cod sursa(job #36292)

Utilizator MariusMarius Stroe Marius Data 23 martie 2007 12:46:22
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
using namespace std;

const char iname[] = "schi.in";
const char oname[] = "schi.out";

#define MAX_N 32768

int cnt[MAX_N];

int n;

int A[MAX_N], R[MAX_N];


#define left(z)  (2 * (z))
#define right(z) (2 * (z) + 1)

void buildTree(int n, int lo, int hi)
{
	cnt[n] = hi - lo + 1;
	if (hi == lo)
		return ;
	int mid = (hi + lo) / 2;
	buildTree(left(n), lo, mid);
	buildTree(right(n), mid + 1, hi);
}

void update(int n, int lo, int hi, int index, int place)
{
	if (hi == lo) {
		R[hi]  = index;
		cnt[n] --;
		return ;
	}
	int mid = (hi + lo) / 2;
	if (place <= cnt[left(n)])
		update(left(n), lo, mid, index, place);
	else
		update(right(n), mid + 1, hi, index, place - cnt[left(n)]);
	cnt[n] = cnt[left(n)] + cnt[right(n)];
}

int main(void)
{
	freopen(iname, "r", stdin);
	int i;
	scanf("%d", & n);
	for (i = 1; i <= n; ++ i)
		scanf("%d", A + i);
	buildTree(1, 1, n);
	for (int i = n; i > 0; -- i)
		update(1, 1, n, i, A[i]);
	freopen(oname, "w", stdout);
	for (int i = 1; i <= n; ++ i)
		printf("%d\n", R[i]);

	return 0;
}