Cod sursa(job #141585)

Utilizator andrei.12Andrei Parvu andrei.12 Data 23 februarie 2008 14:17:01
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<stdio.h>

#define lg 30005

int n, i, v[lg], pz, sol[lg];
struct sgtree{
	int st, dr, v;
};
sgtree q[50000];
void cstr(int nod, int st, int dr){
	q[nod].st = st;
	q[nod].dr = dr;
	if (st == dr){
		q[nod].v = 1;
		return ;
	}
	
	int x = (st+dr) / 2;
	
	cstr(2*nod, st, x);
	cstr(2*nod+1, x+1, dr);
	
	q[nod].v = q[2*nod].v+q[2*nod+1].v;
}
int find(int poz, int val){
	if (q[poz].st == q[poz].dr)
		return q[poz].st;
	
	if (q[2*poz].v >= val)
		return find(2*poz, val);
	else
		return find(2*poz+1, val-q[2*poz].v);
}
void change(int poz, int val){
	q[poz].v --;
	if (q[poz].st == q[poz].dr)
		return ;
	
	if (val <= q[2*poz].dr)
		change(2*poz, val);
	else
		change(2*poz+1, val);
}
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]);
		
		sol[pz] = i;
		//printf("%d %d\n", pz, i);
		
		change(1, pz);
	}
	
	for (i = 1; i <= n; i ++)
		printf("%d\n", sol[i]);
	
	return 0;
}