Cod sursa(job #141590)

Utilizator andrei.12Andrei Parvu andrei.12 Data 23 februarie 2008 14:24:45
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>

#define lg 30005

int n, i, v[lg], pz, sol[lg], q[65000];
void cstr(int nod, int st, int dr){
	if (st == dr){
		q[nod] = 1;
		return ;
	}
	
	int x = (st+dr) / 2;
	
	cstr(2*nod, st, x);
	cstr(2*nod+1, x+1, dr);
	
	q[nod] = q[2*nod]+q[2*nod+1];
}
int find(int poz, int val, int st, int dr){
	if (st == dr)
		return st;
	
	if (q[2*poz] >= val)
		return find(2*poz, val, st, (st+dr) / 2);
	else
		return find(2*poz+1, val-q[2*poz], (st+dr) / 2+1, dr);
}
void change(int poz, int val, int st, int dr){
	q[poz] --;
	if (st == dr)
		return ;
	
	if (val <= (st+dr) / 2)
		change(2*poz, val, st, (st+dr) / 2);
	else
		change(2*poz+1, val, (st+dr) / 2+1, dr);
}
int main()
{
	freopen("schi.in", "rt", stdin);
	freopen("schi.out", "wt", stdout);
	
	scanf("%d", &n);
	for (i = 1; i <= n; i ++)
		scanf("%d", &v[i]);
	
	cstr(1, 1, n);
	
	for (i = n; i; i --){
		pz = find(1, v[i], 1, n);
		
		sol[pz] = i;
		//printf("%d %d\n", pz, i);
		
		change(1, pz, 1, n);
	}
	
	for (i = 1; i <= n; i ++)
		printf("%d\n", sol[i]);
	
	return 0;
}