Cod sursa(job #1843700)

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

struct nod{
	nod *st, *dr;
	unsigned prior;
	int val, sz; } * nil = new nod { nullptr, nullptr, 0, 0, 0 };

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

void print_tree(nod *n){
	if(n == nil) return;
	print_tree(n->st);
	g << n->val << '\n';
	print_tree(n->dr); }

nod *recalc(nod *n){
	n->sz = n->st->sz + n->dr->sz + 1;
	return n; }

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

nod *join(nod *st, nod *dr){
	if(st == nil) return dr;
	if(dr == nil) return st;
	if(st->prior > dr->prior){
		st->dr = join(st->dr, dr);
		return recalc(st); }
	else{
		dr->st = join(st, dr->st);
		return recalc(dr); } }

nod *insert(nod *n, const int poz, const int val){
	assert(poz <= n->sz);
	auto tmp = split(n, poz);
	nod *mid = new nod { nil, nil, (unsigned)rand(), val, 1 };
	return join(join(tmp.first, mid), tmp.second); }

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