Cod sursa(job #473138)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 28 iulie 2010 11:06:22
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<algorithm>
using namespace std;
#define N_MAX 30005

int rez[N_MAX],a[N_MAX],aib[N_MAX];
int i,n;

void update(int poz,int val)
{
	for(int i=poz;i<=n;i+=i&(-i))
		aib[i]+=val;
}

int query(int poz)
{
	int rez=0;
	for(int i=poz;i>0;i-=i&(-i))
		rez+=aib[i];
	return rez;
}

int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);

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

	for(i=n;i;i--)
	{
		int j,step,x;
		for(step=1;step<n;(step<<=1));
		x=n;
		for(j=n;step;(step>>=1))
		{
			int y;
			if(j-step>0)
			{
				y=query(j-step);
				if(y>=a[i])
					j-=step;
				if(y==a[i])
				{
					x=j;
				}
			}
		}
		update(x,-1);
		rez[x]=i;
	}
	
	for(i=1;i<=n;i++)
		printf("%d\n",rez[i]);

	return 0;
}