Cod sursa(job #1812714)

Utilizator andreeainfo_dAndreea Dutulescu andreeainfo_d Data 22 noiembrie 2016 12:26:37
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <bits/stdc++.h>
using namespace std;
int i,n,nn,poz,q;
struct treap
{
    int val, prior, cate;
    treap *left, *right;
    treap(){}
    treap(int val, int prior,int cate,treap *left, treap *right)
    {
        int ll,rr;
        this->val=val;
        this->prior=prior;
        this->left=left;
        this->right=right;
        this->cate=cate;
    }
};
treap *rad, *nil;
void init(treap *&rad)
{
    srand(unsigned(time(0)));
    rad=nil=new treap(0,0,0,NULL,NULL);
}
void update_cate(treap *&nod)
{
    if(nod==nil);
    else nod->cate=nod->left->cate+nod->right->cate+1;
}
int cauta(treap *nod, int nr)
{
    if(nod->left->cate+1==nr)return nod->val;
    else if(nod->left->cate>=nr)return cauta(nod->left,nr);
    else return cauta(nod->right, nr-(nod->left->cate)-1);
}
void rot_left(treap *&nod)
{
    treap *t=nod->left;
    nod->left=t->right;
    t->right=nod;
    update_cate(t);
    update_cate(nod);
    nod=t;
}
void rot_right(treap *&nod)
{
    treap *t=nod->right;
    nod->right=t->left;
    t->left=nod;
    update_cate(t);
    update_cate(nod);
    nod=t;
}
void balance(treap *&nod)
{
    if(nod->left->prior > nod->prior)rot_left(nod);
    else if (nod->right->prior > nod->prior)rot_right(nod);
    update_cate(nod);
}
void inserare(treap *&nod, int val, int prior)
{
    if(nod==nil)
    {
        nod=new treap(val,prior,1,nil,nil);
        return;
    }
    if(val < nod->val)inserare(nod->left, val, prior);
    else if (val > nod->val)inserare(nod->right, val, prior);
    update_cate(nod);
    balance(nod);
}
void stergere(treap *&nod, int val)
{
    if(nod==nil)return;
    if(val < nod->val)stergere(nod->left, val);
    else if(val > nod->val)stergere(nod->right, val);
    else
    {
        if(nod->left==nil&&nod->right==nil)
        {
            delete nod;
            nod=nil;
            return;
        }
        else
        {
            if(nod->left->prior > nod->right->prior)rot_left(nod);
            else rot_right(nod);
            stergere(nod, val);
        }
    }
    update_cate(nod);
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    init (rad);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        q=rand()+1;
        inserare(rad,i,q);
    }
    nn=n;
    poz=1;
    for(i=1;i<=n;i++)
    {
        poz=poz+i-1;
        poz=poz%(n-i+1);
        q=cauta(rad,poz+1);
        printf("%d ",q);
        stergere(rad,q);
        if(poz<0)poz=poz+n-i;
    }
    return 0;
}