Cod sursa(job #1258113)

Utilizator ucc_5Usurelu Catalin ucc_5 Data 8 noiembrie 2014 14:44:12
Problema Statistici de ordine Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <iostream>

using namespace std;

template <class T>
class Node
{
private:
	Node<T> *parent, *left, *right;
	T* info;
	int size;

public:
	Node()
	{
		parent = NULL;
		left = NULL;
		right = NULL;
		size = 0;
	}

	void setInfo(T x)
	{
		info = new T;
		*info = x;
	}

	void insert(T x)
	{
		if(info == NULL)
		{
			setInfo(x);
			size = 1;
		}
		else
		{
			if(x < *info)
			{
				if(left == NULL)
				{
					left = new Node<T>();
					left->parent = this;
				}
				size++;
				left->insert(x);
				
			}
			else if(x > *info)
			{
				if(right == NULL)
				{
					right = new Node<T>();
					right->parent = this;
				}
				right->insert(x);
				
			}	
		}
	}

	T find_k(int k)
	{
		if(size == k)
			return *info;
		else if(size > k)
			return left->find_k(k);
		else if (size < k)
			return right->find_k(k - size);
	}
};

int main()
{
	ifstream f("sdo.in");
	ofstream g("sdo.out");

	int n, k, x;
	Node<int>* root = new Node<int>();

	f >> n >> k;
	for(int i = 0; i < n; i++)
	{
		f >> x;
		root->insert(x);
	}

	g << root->find_k(k);

	return 0;
}