Cod sursa(job #371245)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 4 decembrie 2009 17:28:26
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<stdio.h>
#define left nod<<1
#define right ((nod<<1)+1)
#define mij ((st+dr)>>1)
int n,v[1<<15],sol[1<<15],nr[1<<16];

void init(int nod, int st, int dr)
{
	if(st==dr)
	{
		nr[nod]=1;
		return;
	}
	init(left,st,mij);
	init(right,mij+1,dr);
	nr[nod]=nr[left]+nr[right];
}

int query(int nod, int st, int dr, int x)
{
	if(st==dr)
		return st;
	return (x>nr[left])?query(right,mij+1,dr,x-nr[left]):query(left,st,mij,x);
}

void update(int nod, int st, int dr, int x)
{
	if(st==dr)
	{
		nr[nod]=0;
		return;
	}
	if(mij>=x)
		update(left,st,mij,x);
	if(mij<x)
		update(right,mij+1,dr,x);
	nr[nod]=nr[left]+nr[right];
}

int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	init(1,1,n);
	int x;
	for(i=n;i>=1;i--)
	{
		x=query(1,1,n,v[i]);
		sol[x]=i;
		update(1,1,n,x);
	}
	for(i=1;i<=n;i++)
		printf("%d\n",sol[i]);
	return 0;
}