Cod sursa(job #830892)

Utilizator VincentVegaVincent Vega VincentVega Data 7 decembrie 2012 20:14:44
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#define NMAX 30100
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

int N, sol[NMAX];
int v[NMAX];
int AIB[NMAX];

inline void update(int pos, int val)
{
	for (int i = pos; i <= N; i = (i | (i - 1)) + 1)
	{
		AIB[i] += val;
	}
}

inline int query(int pos)
{
	int res = 0;
	for (int i = pos; i >= 1; i = i & (i - 1))
	{
		res = res + AIB[i];
	}
	return res;
}

inline int bs(int position)
{
	int i = N, cnt = 1 << 20;
	for (; cnt > 0; cnt >>= 1)
	{
		if (i - cnt >= 1)
		{
			if (query(i - cnt) >= position) i -= cnt;
		}
	}
	return i;
}

int main()
{
	fin >> N;
	for (int i = 1; i <= N; ++i)
	{
		fin >> v[i];
	}
	for (int i = 1; i <= N; ++i)
	{
		update(i, 1);
	}
	
	for (int i = N; i >= 1; --i)
	{
		int abc = bs(v[i]);
		sol[abc] = i;
		update(abc, -1);
	}
	
	for (int i = 1; i <= N; ++i)
	{
		fout << sol[i] << '\n';
	}
	fout.close();
	return 0;
}