Cod sursa(job #160650)

Utilizator ProtomanAndrei Purice Protoman Data 16 martie 2008 14:41:57
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#define mx 120010
long i,j,n,s,gs;
long ai[mx];
long b[30010],a[30010];

void add(long nod, long p, long u, long poz, int ct)
{
	long m;
	if (p==u)
	{
		ai[nod]+=ct;
		return;
	}
	if (p<u)
	{
		m=(p+u)/2;
		if (poz<=m)
			add(nod*2,p,m,poz,ct);
		if (m<poz)
			add(nod*2+1,m+1,u,poz,ct);
		ai[nod]=ai[2*nod]+ai[2*nod+1];
	}
}

void query(long nod, long p, long u)
{
	long m;
	if (ai[nod]<s)
	{
		s-=ai[nod];
		return;
	}
	if (p==u && s==1)
	{
		gs=p;
		return;
	}
	if (p<u)
	{
		m=(p+u)/2;
		query(nod*2,p,m);
		if (gs==0)
			query(nod*2+1,m+1,u);
	}
}

int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	scanf("%ld",&n);
	for (i=1; i<=n; i++)
	{
		scanf("%ld",&a[i]);
		add(1,1,n,i,1);
	}
	for (i=n; i>0; i--)
	{
		gs=0;
		s=a[i];
		query(1,1,n);
		b[gs]=i;
		add(1,1,n,gs,-1);
	}
	for (i=1; i<=n; i++)
		printf("%ld\n",b[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}