Pagini recente » Cod sursa (job #23163) | Cod sursa (job #1495036) | Cod sursa (job #1493627) | Cod sursa (job #2438442) | Cod sursa (job #1953307)
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
struct TREAP
{
int key,priority;
TREAP *left,*right;
TREAP() {};
TREAP(int key,int priority,TREAP *left,TREAP*right)
{
this->key=key;
this->priority=priority;
this->left=left;
this->right=right;
}
}*R,*nil;
bool isKeyinTreap(int key,TREAP *node)
{
if(node==nil)
return false;
if(key==node->key)
{
return true;
}
if(key<node->key)
return isKeyinTreap(key,node->left);
else
return isKeyinTreap(key,node->right);
}
void init()
{
R = nil = new TREAP(0, 0, NULL, NULL);
}
void rotateLeft(TREAP* &node)
{
TREAP* aux=node->left;
node->left=aux->right;
aux->right=node;
node=aux;
}
void rotateRight(TREAP* &node)
{
TREAP* aux=node->right;
node->right=aux->left;
aux->left=node;
node=aux;
}
void balaceTreap(TREAP* &node)
{
if(node->left->priority>node->priority)
{
rotateLeft(node);
}
else if(node->right->priority>node->priority)
rotateRight(node);
}
void insertNode(int key,int priority,TREAP* &node,int descazut)
{
if(!isKeyinTreap(key,R))
{
if(descazut!=0)
{
insertNode(key-descazut,priority,R,0);
}
if(node==nil)
{
node=new TREAP(key,priority,nil,nil);
return;
}
if(key<node->key)
insertNode(key,priority,node->left,descazut);
else
insertNode(key,priority,node->right,node->priority);
balaceTreap(node);
}
}
stack <int> st;
void raspuns(TREAP *node)
{
st.push(node->left->key);
raspuns(node->left);
st.push(node->right->key);
raspuns(node->right);
}
int main()
{
int n;
//freopen("order.in","r",stdin);
//freopen("order.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
insertNode((R->key+i)%n,i,R,0);
}
st.push(R->key);
while(!st.empty())
{
printf("%d",st.top());
st.pop();
}
return 0;
}