Cod sursa(job #471080)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 16 iulie 2010 21:00:28
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
//sortare cu treap

#include <iostream>
#include <fstream>
#define nmax 100006

using namespace std;

const char iname[] = "order.in";
const char oname[] = "order.out";

ifstream fin(iname);
ofstream fout(oname);

struct treap
{
	int key, priority, nodes;
	treap *right;
	treap *left;
};

treap *T, *R, *nil;
int i, j, k, N, x, ct, A[nmax], aux;

void getNrNodes(treap *&n)
{
	if(n == nil)
		return;
	else
		n->nodes = n->left->nodes + n->right->nodes + 1;
}

void rotLeft(treap *&n)
{
	treap *t = n -> right;
	n -> right = t -> left;
	t -> left = n;
	getNrNodes (n), getNrNodes (t); 
	n = t;
}
	
void rotRight(treap *&n)
{
	treap *t = n -> left;
	n -> left = t -> right;
	t -> right =  n;
	getNrNodes (n), getNrNodes (t); 
	n = t;
}

	
void balance(treap *&n)
{	
	getNrNodes (n);
	if(n -> left -> priority > n -> priority)
		rotRight(n);
	else
		if(n -> right -> priority  > n -> priority)
			rotLeft(n);
}

void insert(treap *&n, int key, int priority)
{
	if(n == nil)
	{
		n = new treap;
		n -> key = key;
		n -> priority = priority;
		n -> right = nil;
		n -> left = nil;
		n -> nodes = 1;
		return;
	}
	if(key < n -> key)
		insert(n -> left, key, priority);
	else
		insert(n -> right, key, priority);
	balance(n);
}

void init()
{
	nil = new treap;
	nil -> priority = -2;
	nil -> key = 0;
	nil -> right = NULL;
	nil -> left = NULL;
	nil -> nodes = 0;
}

void parcurgere(treap *x)
{	
	if(x == nil)
		return;
	parcurgere(x -> left);
	//A[++ct] = x -> key;
	//fout << A[ct] << " ";
	parcurgere(x -> right);
}
	
int find(treap *&n, int x)
{	
	if(n == nil)
		return 0;
	if(n -> left -> nodes + 1 == x)
		return n -> key;
	else
	{
		if(n -> left -> nodes + 1 < x)
		{
			if(n -> right != nil)
				return find(n -> right, x - n -> left -> nodes - 1);
		}
		else
		{
			if(n -> left != nil)
				return find(n -> left, x);
		}
	}
}	

void sterge(treap *&n, int key)
{
	if(key < n-> key)
		sterge(n -> left, key);
	else
		if(key > n -> key)
			sterge(n -> right, key);
	else
	{
		if(n -> left == nil && n -> right == nil)
		{
			delete n;
			n = nil;
		}
		else
			{
				if(n -> left -> priority > n -> right -> priority)
					rotRight(n);
				else
					rotLeft(n);
				sterge(n, key);
			}
	}
	getNrNodes(n);
}
		
treap *rad;
int K;
int pas;

int main()
{	
	srand(time(NULL));
	init();
	fin >> N;
	R = nil;
	for(i = 1; i <= N; i ++)
		insert(R, i, rand() + 1);
	
	//parcurgere(R);
	
	
	int ct;
	j = 1, pas = 1, i = N;
	int p = N;
	while(N > 0)
	{

		j = (j + pas) % N;
		
		if(pas != 1)
			--j;
		if(j == 0)
			j = N;
		if(j == -1)
			j = N - 1;
		if(pas == p)
			j = 1;
		aux = find(R, j);
		fout << aux << " ";
		sterge(R, aux);
		++pas;
		--N;
	}
			
	//find(R, K);
	return 0;
}