Cod sursa(job #1811364)

Utilizator NinjaCubeMihai Radovici NinjaCube Data 21 noiembrie 2016 10:13:17
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include <bits/stdc++.h>
using namespace std;
int n,p,ras;

struct Treap
{
    int val,pr,sz;
    Treap *lf,*rt;
    Treap(){}
    Treap(int val, int pr, int sz, Treap *lf, Treap *rt)
    {
        this->val=val;
        this->pr=pr;
        this->sz=sz;
        this->lf=lf;
        this->rt=rt;
    }
}*R,*nil;

void reup(Treap * &nod)
{
    nod->sz = nod->lf->sz + nod->rt->sz + 1;
}
void rot_right(Treap *&nod)
{
    Treap *aux = nod->rt;
    nod->rt = aux->lf;
    aux->lf = nod;
    reup(nod);
    reup(aux);
    nod=aux;
}

void rot_left(Treap *&nod)
{
    Treap *aux=nod->lf;
    nod->lf = aux->rt;
    aux->rt = nod;
    reup(nod);
    reup(aux);
    nod=aux;
}

void balance(Treap *&nod)
{
    if(nod->lf->pr > nod->pr)
        rot_left(nod);
    else if(nod->rt->pr > nod->pr)
        rot_right(nod);
}

void ins(Treap *&nod, int val, int pr)
{
    if(nod == nil)
    {
        nod = new Treap(val,pr,1,nil,nil);
        return ;
    }
    if(val < nod->val)
        ins(nod->lf, val, pr);
    else if(val > nod->val)
        ins(nod->rt, val, pr);

    reup(nod);
    balance(nod);
}

void erase(Treap *&nod, int val)
{
    if(nod == nil)
        return ;

    if(val < nod->val)
        erase(nod->lf, val);
    else if(val > nod->val)
        erase(nod->rt, val);
    else
    {
        if(nod->rt == nil && nod->lf == nil)
        {
            delete nod;
            nod=nil;
            return ;
        }
        else
        {
            if(nod->lf->pr > nod->rt->pr)
                rot_left(nod);
            else rot_right(nod);
            //(nod->lf->pr > nod->rt->pr ) ? rot_left(nod) : rot_right;
            erase(nod,val);
        }
    }
    reup(nod);
}
int  sch(Treap *&nod, int val)
{
    if( nod->lf->sz + 1 == val)
        return nod->val;
    else if(nod->lf->sz >= val)
        return sch(nod->lf, val);
    else
        return sch(nod->rt, val - nod->lf->sz - 1);

}
void afis(Treap *&nod)
{
    if(nod == nil)
        return ;
    if(nod->lf == nil && nod->rt == nil)
    {
        //printf(" (%d) ",nod->val);
        printf(" (%d %d %d) ",nod->val,nod->pr, nod->sz);
        return ;
    }
    if(nod->lf != nil)
    {
        afis(nod->lf);
        printf("<-");
    }
        //printf(" (%d) ",nod->val);
        printf(" (%d %d %d) ",nod->val,nod->pr, nod->sz);
    if(nod->rt != nil)
    {
        printf("->");
        afis(nod->rt);
    }
    printf("   ");
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    srand(unsigned(time(0)));
    R = nil = new Treap(0,0,0,NULL,NULL);
    for(int i = 0; i < n; i ++ )
        ins(R, i, rand() + 1);
    p=1;
    //afis(R);
    for(int i = 1; i <= n; i ++ )
    {
        p += i-1;
        p = p  % ( n - i + 1 );
        ras = sch( R, p+1 );
        erase( R, ras);
        //afis(R);printf("\n");
        printf("%d ",ras+1);
        if(p<0)p+=(n-i);
    }
    return 0;
}