Cod sursa(job #253233)

Utilizator AndreyPAndrei Poenaru AndreyP Data 5 februarie 2009 16:21:41
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#include<stdlib.h>
#define N 30010
int n,t[N],v[N];
int sol[N];
inline int nrb(int x)
{
	return (x&(x-1))^x;
}
inline void citire()
{
	scanf("%d",&n);
	for(int i=1; i<=n; ++i)
		scanf("%d",&v[i]);
}
inline void init()
{
	for(int i=1; i<=n; ++i)
		t[i]=nrb(i);
}
void update(int k)
{
	--t[k];
	while((k+=nrb(k))<=n)
		--t[k];
}
int suma(int k)
{
	int s=0;
	while(k)
	{
		s+=t[k];
		k-=nrb(k);
	}
	return s;
}
int afla(int val)
{
	int p=1,u=n,m;
	while(p<u)
	{
		m=(p+u)>>1;
		if(suma(m)>=val)
			u=m;
		else
			p=m+1;
	}
	return p;
}
inline void rezolva()
{
	for(int i=n; i; --i)
	{
		int aux=afla(v[i]);
		sol[aux]=i;
		update(aux);
	}
}
inline void scrie()
{
	for(int i=1; i<=n; ++i)
		printf("%d\n",sol[i]);
}
int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	citire();
	init();
	rezolva();
	scrie();
	return 0;
}