Cod sursa(job #1978301)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 7 mai 2017 13:25:50
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <fstream>
#include <cstdlib>
#include <ctime>
#define inf 1e9
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 == nil)
    {
        t = new treap(key,pr,nil,nil);
        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)
{
    if(t == nil)
        return;

    if(t->key > key)
        dell(t->st,key);
    else if(t->key<key)
        dell(t->dr,key);
    else
    {
        if (t->st == NULL && t->dr==NULL)
        {
            delete t;
            t = nil;
        }
        else
        {
            if (t->st->pr > t->dr->pr)
                right(t);
            else
                left(t);
            dell(t,key);
        }
    }
}

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,x = 1;
    for (int i=1;i<=n;i++)
    {
        x = (x+i)%nr;
        if (x==0)
            x = nr;
        g<<_find(T,x)<<'\n';
        dell(T,_find(T,x));
        nr--;
    }


    return 0;
}