Cod sursa(job #2074373)

Utilizator flibiaVisanu Cristian flibia Data 24 noiembrie 2017 15:31:23
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 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], p;

void update(int st, int dr, int pos, int idx, int val){
	if(st == dr){
		h[pos] = val;
		return;
	}
	int mid = (st + dr) >> 1;
	if(idx <= mid)
		update(st, mid, L, idx, val);
	else 
		update(mid + 1, dr, R, idx, val);
	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];
	for(int i = 1; i <= n; i++)
		update(1, n, 1, i, 1); 
	for(int i = n; i >= 1; i--){
		query(1, n, 1, a[i], 0, i);
		update(1, n, 1, p, 0);
	}
	for(int i = 1; i <= n; i++)
		out << sol[i] << '\n';
	return 0;
}