Cod sursa(job #931250)

Utilizator fhandreiAndrei Hareza fhandrei Data 28 martie 2013 09:14:07
Problema Schi Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
// Include
#include <fstream>
using namespace std;

// Structuri
struct type_node
{
	int id;
	int currentPos;
	int add;
	type_node *leftSon, *rightSon;
	type_node()
	{
		id = 0;
		currentPos = 0;
		add = 0;
		leftSon = rightSon = '\0';
	}
};

// Functii
void insert(type_node *node, int dif);
void findAnswer(type_node *node);

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

int num;
int pos, current;

type_node *root = new type_node;

// Main
int main()
{
	in >> num;
	
	in >> current;
	root->id = root->currentPos = 1;
	
	for(pos=2 ; pos<=num ; ++pos)
	{
		in >> current;
		insert(root, 0);
	}
	
	findAnswer(root);
	
	in.close();
	out.close();
	return 0;
}

void insert(type_node *node, int dif)
{
	if(current <= node->currentPos + dif)
	{
		if(!node->leftSon)
		{
			node->leftSon = new type_node;
			node->leftSon->id = pos;
			node->leftSon->currentPos = current - dif - node->add;
			
			++node->currentPos;
			++node->add;
			return;
		}
		insert(node->leftSon, dif);
		++node->currentPos;
		++node->add;
	}
	else
	{
		if(!node->rightSon)
		{
			node->rightSon = new type_node;
			node->rightSon->id = pos;
			node->rightSon->currentPos = current - dif - node->add;
			
			return;
		}
		insert(node->rightSon, dif+node->add);
	}
}

void findAnswer(type_node *node)
{
	if(node->leftSon)
		findAnswer(node->leftSon);
	
	out << node->id << '\n';
	
	if(node->rightSon)
		findAnswer(node->rightSon);
}