Cod sursa(job #979139)

Utilizator cont_de_testeCont Teste cont_de_teste Data 31 iulie 2013 21:02:29
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;

const char iname[] = "schi.in";
const char oname[] = "schi.out";

ifstream fin(iname);
ofstream fout(oname);

const int nmax = 30100;
int n;
int a[nmax], sol[nmax];

//---------------------------------------------------------

int aib[nmax];
inline void add(const int &position, const int &number) {
	for (int i = position; i <= n; i = (i | (i - 1)) + 1)
		aib[i] += number;
}
inline int query(const int &position) {
	int res = 0;
	for (int i = position; i >= 1; i = i & (i - 1))
		res = res + aib[i];
	return res;
}

inline int binsrc_log_patrat(const int &add) {
	int i = 0, cnt = 1 << 15;
	for (; cnt; cnt >>= 1)
		if (i + cnt <= n && add + query(i + cnt) > i + cnt)
			i += cnt;
	return i + 1;
}
inline int binsrc(int add) {
	int i = 0, cnt = 1 << 15;
	for (; cnt; cnt >>= 1)
		if (i + cnt <= n && add + aib[i + cnt] > i + cnt) {
			i += cnt;
			add += aib[i];
		}
	return i + 1;
}

//---------------------------------------------------------

int main() {
	fin >> n;
	for (int i = 1; i <= n; i++)
		fin >> a[i];
	
	for (int i = n; i >= 1; i--) {
		int position = binsrc(a[i]);
		sol[position] = i;
		add(position, 1);
	}

	for (int i = 1; i <= n; i++)
		fout << sol[i] << '\n';
	fin.close();
	fout.close();
}

//---------------------------------------------------------