Cod sursa(job #1953307)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 4 aprilie 2017 19:14:20
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#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;
}