Cod sursa(job #1175975)

Utilizator andreiiiiPopa Andrei andreiiii Data 25 aprilie 2014 11:46:35
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <algorithm>
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

ifstream fin("order.in");
ofstream fout("order.out");

struct Treap {
    int key, pry, size;
    Treap *left, *right;

    Treap() {}
    Treap(const int _key, const int _pry, const int _size, Treap *_left, Treap *_right)
    {
        key=_key;
        pry=_pry;
        size=_size;
        left=_left;
        right=_right;
    }
};

Treap *Root, *NIL;

void Update(Treap* &node)
{
    node->size=node->left->size+node->right->size+1;
}

void RotLeft(Treap* &node)
{
    Treap *t=node->left;
    node->left=t->right;
    t->right=node;
    node=t;

    Update(node->right);
    Update(node);
}

void RotRight(Treap* &node)
{
    Treap *t=node->right;
    node->right=t->left;
    t->left=node;
    node=t;

    Update(node->left);
    Update(node);
}

int get_rand()
{
    int ret=(rand()%32768)*10000+rand()%32768;
    if(ret<0) ret=-ret;
    if(!ret) ret++;
    return ret;
}

void Balance(Treap* &node)
{
    if(node->left->pry>node->pry) RotLeft(node);
    else if(node->right->pry>node->pry) RotRight(node);
}

void Insert(Treap* &node, int key, int pry)
{
    if(node==NIL)
    {
        node=new Treap(key, pry, 1, NIL, NIL);
        return;
    }

    if(key<node->key) Insert(node->left, key, pry);
    else if(key>node->key) Insert(node->right, key, pry);

    Update(node);
    Balance(node);
}

int NthElement(Treap* &node, int poz)
{
    if(node->left->size>=poz) return NthElement(node->left, poz);
    if(node->left->size+1==poz) return node->key;
    return NthElement(node->right, poz-node->left->size-1);
}

void Erase(Treap* &node, int key)
{
    if(node==NIL) return;

    if(node->key==key)
    {
        if(node->left==NIL&&node->right==NIL)
        {
            delete node;
            node=NIL;
            return;
        }
        if(node->left->pry>node->right->pry) RotLeft(node);
        else RotRight(node);
        Erase(node, key);
    }
    else if(key<node->key) Erase(node->left, key);
    else Erase(node->right, key);

    Update(node);
}

void Init()
{
    srand(time(0));
    Root=NIL=new Treap(0, 0, 0, NULL, NULL);
}

int main()
{
    Init();

    int N;
    fin>>N;

    for(int i=1;i<=N;i++) Insert(Root, i, get_rand());
    for(int i=1, j=0;i<=N;i++)
    {
        j=(j+i)%(N-i+1);
        int x=NthElement(Root, j+1);
        fout<<x<<" ";
        Erase(Root, x);

        j--;

    }
    fout<<"\n";

    fin.close();
    fout.close();
}