Cod sursa(job #458197)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 23 mai 2010 19:35:30
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <cstdio>

#define file_in "schi.in"
#define file_out "schi.out"

#define zero(x) ((x^(x-1))&x)
#define nmax 30100

int n,v[nmax],aib[nmax],ord[nmax];

void add(int poz, int val)
{
	int i;
	
	for (i=poz;i<=n;i+=zero(i))
		  aib[i]+=val;
}

int query(int x)
{
	int i,rez=0;
	for (i=x;i>=1;i-=zero(i))
		 rez+=aib[i];
	return rez;
}



void citire()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d", &n);
	for (int i=1;i<=n;++i)
	{
		scanf("%d", &v[i]);
		add(i,1);
	}
}

int cautare(int X)
{
	int i,step;
	
	for (step=1;step<=n;step<<=1); 
	step>>=1;
	for (i=n;step;step>>=1)
		 if (i-step>=1 && query(i-step)>=X)
				  i-=step;
	return i;
}	
				  

void solve()
{
	int i,poz;
	
	for (i=n;i>=1;--i)
	{
		poz=cautare(v[i]);
		ord[poz]=i;
		add(poz,-1);
	}
	
	for (i=1;i<=n;++i)
		 printf("%d\n", ord[i]);
}


int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}