Cod sursa(job #1668923)

Utilizator lupvasileLup Vasile lupvasile Data 30 martie 2016 10:33:46
Problema Schi Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>
using namespace std;
#ifdef INFOARENA
#define cout fout
#endif // INFOARENA
ifstream fin("schi.in");
ofstream fout("schi.out");
/// ////////////////////////////////

struct N_TREAP
{
    short ind,nr;
    int priority;
    N_TREAP *left,*right;

} *nil = new N_TREAP {0,0,0,NULL,NULL};

class C_TREAP
{
private:
    N_TREAP *root=nil;

    void update_sons(N_TREAP *n)
    {
        n->nr = n->left->nr + n->right->nr + 1;
    }

    void rot_left(N_TREAP *&n)
    {
        N_TREAP *son = n->left;
        n->left = son->right;
        son->right = n;

        update_sons(n);
        update_sons(son);

        n=son;
    }

    void rot_right(N_TREAP *&n)
    {
        N_TREAP *son = n->right;
        n->right = son->left;
        son->left = n;

        update_sons(n);
        update_sons(son);

        n=son;
    }

    void balance(N_TREAP *&n)
    {
        if(n->left->priority > n->priority) rot_left(n);
        else if(n->right->priority > n->priority) rot_right(n);
    }

    void insert(N_TREAP *&n,short ind,short pos)
    {
        if(n==nil)
        {
            n= new N_TREAP{ind,1,rand()+1,nil,nil};
            return;
        }

        if(pos<=n->left->nr+1) insert(n->left,ind,pos);
        else insert(n->right,ind,pos-n->left->nr-1);

        balance(n);
    }

    void dfs(N_TREAP *n)
    {
        if(n==nil) return;
        dfs(n->left);
        cout<<n->ind<<'\n';
        dfs(n->right);
    }
public:
    void add(int ind,int pos)
    {
        insert(root,ind,pos);
    }

    void show()
    {
        dfs(root);
    }

} treap;

int main()
{
    int i,n,x;
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>x;
        treap.add(i,x);
    }
    treap.show();
    return 0;
}