Cod sursa(job #409474)

Utilizator xtephanFodor Stefan xtephan Data 3 martie 2010 18:06:31
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<stdio.h>

int arb[180001];
int c[30001];
int v[30001];
int n;


void cit();
void rez();
void afis();

int main() {
	
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);
	
	cit();
	rez();
	afis();
	
	return 0;
}

void update(int i, int j, int p, int nod, int val) {
	
	if(i==j && j==p) {
		arb[nod]=val;
		return;
	}
	
	int mij=(i+j)/2;
	
	if(p<=mij)
		update(i,mij,p,nod*2,val);
	else
		update(mij+1,j,p,nod*2+1,val);
	
	arb[nod]=arb[nod*2]+arb[nod*2+1];
}


void cit() {
	scanf("%d", &n);
	for(int i=1; i<=n;i++)
		scanf("%d", &v[i]), update(1,n,i,1,1);
}

int query(int i, int j, int nod, int val) {
	
	if(i==j)
		//return arb[nod];
		return i;
	
	int mij=(i+j)/2, r=0;
	
	if(val<=arb[nod*2])
		return query(i,mij,nod*2,val);
	else
		return query(mij+1,j,nod*2+1,val-arb[nod*2]);
	
}

void rez() {
	
	int i,j;
	
	for(i=n; i>=1; --i) {
		
		int tmp=query(1,n,1,v[i]);
		c[tmp]=i;
		update(1,n,tmp,1,0);
		
	}
	
}


void afis() {
	for(int i=1; i<=n; i++)
		printf("%d\n", c[i]);
}