Cod sursa(job #141540)

Utilizator savimSerban Andrei Stan savim Data 23 februarie 2008 13:17:36
Problema Schi Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <stdio.h>
#define maxl 33000
int put,i,j,k,n;
int a[maxl],c[maxl],fin[maxl];
void parc(int poz)
{
	if ((1<<put)-1<poz)
	{
		k-=c[poz];
		fin[poz-(1<<put)+1]=i;
		c[poz]=0;
		return;
	}
	if (c[poz*2]<k)
	{
		k-=c[poz*2];
		parc(poz*2+1);
	}
	else parc(poz*2);

	c[poz]=c[poz*2]+c[poz*2+1];
}
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]);

	put=0;
	for (i=0; i<=n; i++)
		if ((1<<i)>=n)
		{
			put=i;
			break;
		}
	for (i=1<<put; i<=(1<<put)+n-1; i++)
		c[i]=1;

	for (i=put-1; i>=0; i--)
	{
		for (j=1<<i; j<=(1<<(i+1))-1; j++)
			c[j]=c[2*j]+c[2*j+1];
	}
    
	for (i=n; i>=1; i--)
	{
		k=a[i];
		parc(1);
	}

	for (i=1; i<=n; i++)
		printf("%d\n",fin[i]);

    return 0;    
}