Cod sursa(job #2306268)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 21 decembrie 2018 21:01:06
Problema Schi Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<bits/stdc++.h>
using namespace std;

struct Treap
{
    int priority;
    int key;
    int weight;
    Treap *left,*right;
    Treap(int priority,int key,int weight,Treap *left,Treap *right)
    {
        this->priority=priority;
        this->key=key;
        this->weight=weight;
        this->left=left;
        this->right=right;
    }
}*root,*nil;

void setup()
{
    srand(time(0));
    root=nil=new Treap(0,0,0,NULL,NULL);
}

inline int Rand()
{
     return 1 + (((rand()%32768)<<15) + rand()%32768 + 1 );
}

void update_weight(Treap *node)
{
    if(node==nil) node->weight=0;
        else node->weight=1+node->left->weight+node->right->weight;
}

void rotright(Treap* &node)
{
    Treap *w=node->left;
    node->left=w->right;
    w->right=node;
    node=w;
}

void rotleft(Treap* &node)
{
    Treap *w=node->right;
    node->right=w->left;
    w->left=node;
    node=w;
}

void balance(Treap* &node)
{
    if(root->priority<root->left->priority)
    {
        rotright(node);
        update_weight(node->right);
        update_weight(node);
    }
        else
    if(root->priority<root->right->priority)
    {
        rotleft(node);
        update_weight(node->left);
        update_weight(node);
    }
}

void insert_node(Treap* &node,int pos,int priority,int key)
{
    if(node==nil)
    {
        node=new Treap(priority,key,1,nil,nil);
    }
        else
    {
        if(node->left->weight>=(pos-1)) insert_node(node->left,pos,priority,key);
                else insert_node(node->right,pos-node->left->weight-1,priority,key);

        balance(node);
        update_weight(node);
    }
}

void dfs(Treap *node)
{
    if(node==nil) return;
    update_weight(node);
    dfs(node->left);
    printf("%d\n",node->key);
    dfs(node->right);
}
int n,x;
int main()
{
    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);

    scanf("%d",&n);

    setup();

    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        insert_node(root,x,Rand(),i);
    }

    dfs(root);

    return 0;
}