Cod sursa(job #1813383)

Utilizator StefansebiStefan Sebastian Stefansebi Data 22 noiembrie 2016 22:19:44
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");

int arb[100009];

void update(int n, int l, int r, int pos, int val) {
	if (l == r) {
		arb[n] = val;
		return;
	}
	int m = (l + r) / 2;
	if (pos <= m) {
		update(n * 2, l, m, pos, val);
	}
	else {
		update(n * 2 + 1, m + 1, r, pos, val);
	}
	arb[n] = arb[n * 2] + arb[n * 2 + 1];
}

void query(int n, int l, int r, int i, int& pos) {
	if (l == r) {
		pos = l;
		return;
	}
	int m = (l + r) / 2;
	if (i <= arb[n * 2]) {
		query(n * 2, l, m, i, pos);
	}
	else {
		query(n * 2 + 1, m + 1, r, i - arb[n * 2], pos);
	}
}


int main() {
	int n;
	fin >> n;
	int v[100009], r[100009];
	for (int i = 1; i <= n; i++) {
		fin >> v[i];
		update(1, 1, n, i, 1);
	}
	for (int i = n; i >= 1; i--) {
		int pos;
		query(1, 1, n, v[i], pos);
		r[pos] = i;
		update(1, 1, n, pos, 0);
	}
	for (int i = 1; i <= n; i++) {
		fout << r[i] << "\n";
	}
}