Cod sursa(job #1248146)

Utilizator sorin2kSorin Nutu sorin2k Data 24 octombrie 2014 18:47:37
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<iostream>
using namespace std;

int aib[30002], n, v[30002], fin[30002];

void update(int poz, int val) {
	while(poz <= n) {
		aib[poz] += val;
		poz += poz & -poz;
	}
}

int query(int poz) {
	int ans = 0;
	while(poz > 0) {
		ans += aib[poz];
		poz -= poz & -poz;
	}
	return ans;
}

// cauta pozitia x a.i. suma primelor x nr. sa fie val
int binar(int val) {
	int lo = 1, hi = n, m, q, ans = -1;
	while(lo <= hi) {
		m = (lo + hi) / 2;
		q = query(m);
		if(q >= val) hi = m-1, ans = m;
		else lo = m+1;
	}
	return ans;
}

int main() {
	freopen("schi.in", "r", stdin);
	freopen("schi.out", "w", stdout);
	int i, val;
	cin >> n;
	for(i = 1; i <= n; i++) {
		cin >> v[i];
		update(i, 1);
	}
	for(i = n; i >= 1; i--) {
		val = binar(v[i]);
		fin[val] = i;
		update(val, -1);
	}
	for(i = 1; i <= n; i++) {
		cout << fin[i] << " ";
	}
	return 0;
}