Cod sursa(job #532082)

Utilizator SadmannCornigeanu Calin Sadmann Data 10 februarie 2011 20:16:49
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#define MAXN 30005
FILE *in,*out;
int n,X,i,Arb[MAXN*4+100],a[MAXN],rez[MAXN];

void update(int,int,int,int,int);
int query(int,int,int,int);

int main()
{
	in=fopen("schi.in","rt");
	out=fopen("schi.out","wt");
	fscanf(in,"%d",&n);
	for(i=1;i<=n;i++)
	{
		fscanf(in,"%d",&a[i]);
		update(1,1,n,i,1);		
	}
	
	for(i=n;i>=1;i--)
	{
		X=query(1,1,n,a[i]);
		update(1,1,n,X,0);
		rez[X]=i;
	}
	for(i=1;i<=n;i++)
		fprintf(out,"%d\n",rez[i]);
	
	
	return 0;
}

void update(int nod,int left,int right,int poz,int val)
{
	if(left==right)
	{
		Arb[nod]=val;
		return;
	}
	int div=(left+right)/2;
	if(poz<=div)
		update(nod*2,left,div,poz,val);
	else
		update(nod*2+1,div+1,right,poz,val);
	Arb[nod]=Arb[nod*2]+Arb[nod*2+1];
	
}

int query(int nod,int left,int right, int val)
{
	if(left==right)
		return right;
	
	int div=(left+right)/2;
	if(val<=Arb[nod*2])
		return query(nod*2,left,div,val);
	else
		return query(nod*2+1,div+1,right,val-Arb[nod*2]);
}