Cod sursa(job #2074356)

Utilizator flibiaVisanu Cristian flibia Data 24 noiembrie 2017 15:21:31
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
#define L 2 * pos
#define R 2 * pos + 1

using namespace std;

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

int n, a[30100], h[120100], sol[30100], x, p;

void build(int st, int dr, int pos){
	if(st == dr){
		h[pos] = 1;
		return;
	}
	int mid = (st + dr) >> 1;
	build(st, mid, L);
	build(mid + 1, dr, R);
	h[pos] = h[L] + h[L];
}

void update(int st, int dr, int pos, int idx){
	if(st == dr){
		h[pos] = 0;
		return;
	}
	int mid = (st + dr) >> 1;
	if(idx <= mid)
		update(st, mid, L, idx);
	else 
		update(mid + 1, dr, R, idx);
	h[pos] = h[L] + h[R];
}	

void query(int st, int dr, int pos, int nr, int cur, int idx){
	if(st == dr){
		sol[st] = idx;
		p = st;
		return;
	}
	int mid = (st + dr) >> 1;
	if(cur + h[L] >= nr)
		query(st, mid, L, nr, cur, idx);
	else 
		query(mid + 1, dr, R, nr, cur + h[L], idx);
}

int main(){
	in >> n;
	for(int i = 1; i <= n; i++)
		in >> a[i];
	build(1, n, 1); 
	for(int i = n; i >= 1; i--){
		query(1, n, 1, a[i], 0, i);
		update(1, n, 1, p);
	}
	for(int i = 1; i <= n; i++)
		out << sol[i] << '\n';
	return 0;
}