Cod sursa(job #170909)

Utilizator amadaeusLucian Boca amadaeus Data 3 aprilie 2008 14:31:43
Problema Schi Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <stdio.h>

#define NX 30010

int N, v[ NX ], T[ NX ], f[ NX ];

void upd( int x, int y ) {
	for( ; x <= N; x += (-x & x) )
		T[ x ] += y;
}

int main() {
	int i, p, m, mask;
	
	freopen( "schi.in", "r", stdin );
	freopen( "schi.out", "w", stdout );

	scanf( "%d", &N );

	for( i = 1; i <= N; i++ )
		scanf( "%d", v + i );

	for( i = 1; i <= N; i++ )
		upd( i, 1 );

	for( mask = 1; mask <= N; mask <<= 1 );
	mask >>= 1;
	
	for( i = N; i; i-- ) {
		for( p = 0, m = mask; m; m >>= 1 )
			if( ( p+m <= N ) && (T[ p+m ] < v[i]) )
				p += m, v[i] -= T[p];
		f[++p] = i;
		upd( p, -1 );
	}

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

	return 0;
}