Cod sursa(job #657007)

Utilizator crushackPopescu Silviu crushack Data 5 ianuarie 2012 17:10:43
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>
#include <string.h>
#define NMax 30010
#define zeros(x) ( x^(x-1)&x )

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

int N;
int v[NMax];
int aib[NMax] , Sol[NMax] , p[NMax];

void Update(int x,int v){
	for (;x<=N ; x+=zeros(x))
		aib[x]+=v;
}

int Query(int x){
	int ret=0;
	for ( ; x>0 ; x-=zeros(x))
		ret+=aib[x];
	return ret;
}

char *waib(){
	static char s[256],*r;
	r=s;
	for (int i=1;i<=N;++i)
	{
		sprintf(r,"%d ",Query(i)-Query(i-1));
		while (*r) ++r;
	}
	*r=0;
	return s;
}

int search(int x)
{
	int i,step;
	for (step=1;step<N;step<<=1);
	for (i=0;step;step>>=1)
		if (i+step<=N && x>=aib[i+step])
			i+=step,x-=aib[i];
	return i;
}

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