Cod sursa(job #574646)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 7 aprilie 2011 13:31:47
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<stdio.h>
#define Nmax 30010

int Aib[Nmax],n,i,v[Nmax],sol[Nmax],val,poz;

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

int query ( int poz ) 
{
	int i, s = 0 ;
	
	for( i = poz ; i ; i -= (i&(-i)) ) 
		s += Aib[i] ; 
	
	return s ;
}

int bsearch ( int x ) 
{
	int s = 1 , d = n , m, suma, ret = 0 ;
	
	for( m = (s+d)>>1 ; s <= d ; m = (s+d)>>1 )
	{
		suma = query(m) ;
		if( suma >= x ) d = m - 1 , ret = m ; 
		else			s = m + 1 ; 
	}
	
	return ret ; 
}

int main()
{
	freopen("schi.in","r",stdin);
	freopen("schi.out","w",stdout);
	
	scanf("%d",&n);   
	
	val = 1 ; 
	for( i = 1 ; i <= n ; i++ )
	{
		scanf("%d",&v[i]);
		update(i);
	}
	
	val = -1 ;
	for( i = n ; i ; i-- )
	{
		poz = bsearch(v[i]);
		sol[poz] = i ;
		update(poz);
	}
	
	for( i = 1 ; i <= n ; i++ )
		printf("%d\n",sol[i]);
	
	return 0 ;
}