Cod sursa(job #613111)

Utilizator darrenRares Buhai darren Data 16 septembrie 2011 11:23:13
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>

using namespace std;

int N;
int P[30002], AIB[30002];
int res[30002];

void add(int pos)
{
	for (; pos <= N; pos += (pos & -pos))
		++AIB[pos];
}
int lower(int pos)
{
	int sum = 0;
	for (; pos >= 1; pos -= (pos & -pos))
		sum += AIB[pos];
	return sum;
}

int main()
{
	ifstream fin("schi.in");
	ofstream fout("schi.out");
	
	fin >> N;
	for (int i = 1; i <= N; ++i)
		fin >> P[i];
	
	int powN;
	for (powN = 1; (powN << 1) <= N; powN <<= 1);
	
	for (int i = N; i >= 1; --i)
	{
		int step = powN, now = 0;
		for (now = 0; step; step >>= 1)
			if (now + step <= N && now + step - lower(now + step) < P[i])
				now += step;
		++now;
		
		res[now] = i;
		add(now);
	}
	
	for (int i = 1; i <= N; ++i)
		fout << res[i] << '\n';
	
	fin.close();
	fout.close();
}