Cod sursa(job #1843702)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 9 ianuarie 2017 07:36:48
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>
using namespace std;

struct nod{
	int st, dr, sz;
	unsigned prior; };

nod nods[(int)3e4 + 100] = {};

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

void print_tree(int n){
	if(!n) return;
	print_tree(nods[n].st);
	g << n << '\n';
	print_tree(nods[n].dr); }

int recalc(int n){
	nods[n].sz = 1 + nods[nods[n].st].sz + nods[nods[n].dr].sz;
	return n; }

pair<int, int> split(int n, const int nr){
	if(nr == 0) return make_pair(0, n);
	if(nr == nods[n].sz) return make_pair(n, 0);
	if(nr >= nods[nods[n].st].sz+1){
		auto tmp = split(nods[n].dr, nr - nods[nods[n].st].sz - 1);
		nods[n].dr = tmp.first;
		return make_pair(recalc(n), tmp.second); }
	else{
		auto tmp = split(nods[n].st, nr);
		nods[n].st = tmp.second;
		return make_pair(tmp.first, recalc(n)); } }

int join(int st, int dr){
	if(st == 0) return dr;
	if(dr == 0) return st;
	if(nods[st].prior > nods[dr].prior){
		nods[st].dr = join(nods[st].dr, dr);
		return recalc(st); }
	else{
		nods[dr].st = join(st, nods[dr].st);
		return recalc(dr); } }

int insert(int n, const int poz, const int val){
	auto tmp = split(n, poz);
	nods[val].prior = rand();
	nods[val].sz = 1;
	return join(join(tmp.first, val), tmp.second); }

int main(){
	int n;
	f >> n;
	int rad = 0;
	for(int i = 0, poz; i < n; ++i){
		f >> poz;
		rad = insert(rad, poz-1, i+1); }
	
	print_tree(rad);
	return 0; }