Cod sursa(job #1978241)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 7 mai 2017 10:57:42
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <fstream>
using namespace std;

ifstream f("order.in");
ofstream g("order.out");

int n;

struct treap{
    int key,pr,nr;
    treap *st,*dr;

    treap(int _key, int _pr, treap *_st, treap *_dr) : key(_key) , pr(_pr) , st(_st) , dr(_dr) , nr(0){};
}*T,*nil;

void right(treap *&t)
{
    treap *x = t->st;
    t->st = x->dr;
    x->dr = t;
    t = x;
    t->dr->nr = t->dr->st->nr + t->dr->dr->nr + 1;
    t->nr = t->st->nr + t->dr->nr +1;
}

void left(treap *&t)
{
    treap *x = t->dr;
    t->dr = x->st;
    x->st = t;
    t = x;
    t->st->nr = t->st->st->nr + t->st->dr->nr + 1;
    t->nr = t->st->nr + t->dr->nr +1;
}

void balance(treap *&t)
{
    if(t->st->pr > t->pr)
        right(t);
    else if (t->dr->pr > t->pr)
        left(t);
}

void add(treap *&t,int key,int pr)
{
    if (t == nill)
    {
        t->st = nill;
        t->dr = nill;
        t->key = key;
        t->pr = pr;
        t->nr = 1;
    }
    else if (t->key > key)
    {
        t->nr++;
        add(t->st,key,pr);
    }
    else if (t->key < key)
    {
        t->nr++;
        add(t->dr,key,pr);
    }

    balance(t);
}

int _find(treap *&t,int x)
{
    if (t->st->nr+1==x)
        return t->key;
    else if (t->st->nr>x)
        return _find(t->st,x);
    else
        return _find(t->dr,x);
}

void dell(treap *&t,int key)
{
    treap *l,*r;
    split(t,key,l,r);
}

int main()
{
    srand(time(0));
    f>>n;
    T = nil = new treap (0,0,NULL,NULL);
    for (int i=1;i<=n;i++)
        add(T,i,rand()+1);

    int nr = n;
    for (i=1;i<=n;i++)
    {
        int x = i%nr;
        if (x==0)
            x = nr;
        g<<_find(T,x);
        dell(T,_find(T,x));
    }


    return 0;
}