Cod sursa(job #40685)

Utilizator webspiderDumitru Bogdan webspider Data 27 martie 2007 17:19:19
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <stdio.h>
#include <iostream>

using namespace std;

int sir[30001];
int n;

int poz[30001];
int in[30001];
int i,j;
int pozc,ad,x;

void ADD( int poz, int val );
int SUM( int poz );

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

	scanf("%d\n", &n);

	for ( i = 1; i <= n; ++i )
		scanf("%d\n", &poz[i] );
	
	for ( i = n; i >= 1; --i )
	{
		pozc = poz[i];
		ad = 0;
		x = SUM( pozc );
		while ( ad != x ) {
			pozc += ( x - ad );
			ad += ( x - ad );
			x = SUM( pozc );
		}
		in[ pozc ] = i;
		ADD( pozc, 1 );
	}

	for ( i = 1; i <= n; i++ )
		printf("%d\n", in[i] );
	
	fclose(stdin);
	fclose(stdout);

	return 0;
}

inline int lsb( int a )
{
	return a ^ ( a & ( a-1 ) );
}

void ADD( int poz, int val )
{
	int p = 0;
	while ( poz <= n )
	{
		sir[ poz ] += val;
		poz+=( lsb( poz ) );
	}
}

int SUM( int poz )
{
	int s = 0, p = 0;

	while ( poz > 0 )
	{
		s += sir[ poz ];
		poz -= ( lsb( poz ) );
	}

	return s;
}