Pagini recente » Cod sursa (job #856328) | Cod sursa (job #1676077) | Cod sursa (job #3255739) | Cod sursa (job #2511720) | Cod sursa (job #471080)
Cod sursa(job #471080)
//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;
}