Cod sursa(job #1258416)

Utilizator Mr.DoomRaul Ignatus Mr.Doom Data 8 noiembrie 2014 20:44:40
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
using namespace std;

ifstream is("schi.in");
ofstream os("schi.out");

void Update(int pos, int val);
int Bs(int val);

int aib[30001];
int n;
int a[30001];
int b[30001];

int main()
{
	is >> n;
	for ( int i = 1; i <= n; ++i )
	{
		is >> a[i];
		Update(i, 1);
	}
	int pos;
	for ( int i = n; i > 0; --i )
	{
		pos = Bs(a[i]);
		b[pos] = i;
		Update(pos, -1);
	}
	for ( int i = 1; i <= n; ++i )
		os << b[i] << '\n';
	
	is.close();
	os.close();
	return 0;
}

void Update(int pos, int val)
{
	for ( int i = pos; i <= n; i += i & -i )
		aib[i] += val;
}
int Bs(int val)
{
	int i = 0;
	for ( int p = 1 << 15; p; p >>= 1)
		if ( i + p <= n && aib[i + p] < val )
		{
			val -= aib[i + p];
			i += p;
		}
	return i + 1;
}