Cod sursa(job #583991)

Utilizator crushackPopescu Silviu crushack Data 23 aprilie 2011 15:07:08
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#define NMax 30010

const char IN[]="schi.in",OUT[]="schi.out";

int N;
int arb[NMax<<1];
int a[NMax];
int R[NMax];

void Update(int *arb,int p,int st,int dr,int x,int val)
{
	if (st==dr)
	{
		arb[p]=val;
		return;
	}
	int m=st+dr>>1;
	if (x<=m) Update(arb,2*p,st,m,x,val);
	else      Update(arb,2*p+1,m+1,dr,x,val);
	arb[p]=arb[2*p]+arb[2*p+1];
}

int Query(int *arb,int K)
{
	int p=1,st=1,dr=N;
	while (st<dr)
	{
		if (K<=arb[2*p])
			dr=st+dr>>1,
			p=2*p;
		else
			st=(st+dr>>1)+1,
			K-=arb[2*p],
			p=2*p+1;
	}
	return dr;
}

int main()
{
	int i,p;
	freopen(IN,"r",stdin);
	scanf("%d",&N);
	for (i=0;i<N;++i)
		scanf("%d",a+i),
		Update(arb,1,1,N,i+1,1);
	fclose(stdin);
	
	for (i=N;i>0;--i)
	{
		R[p=Query(arb,a[i-1])]=i;
		Update(arb,1,1,N,p,0);
	}
	
	freopen(OUT,"w",stdout);
	for (i=1;i<=N;++i)
		printf("%d\n",R[i]);
	fclose(stdout);
	
	return 0;
}