Cod sursa(job #2007518)

Utilizator mari2001Maria Ionescu mari2001 Data 3 august 2017 09:36:02
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include<bits/stdc++.h>
using namespace std;
struct T
{
    int key,pr,sz;
    T *l,*r;
    T()
        {
        this->pr=INT_MIN;
        this->sz=0;
        this->l=NULL;
        this->r=NULL;
        }
    T(int key,int pr,T *l,T *r)
        {
        this->key=key;
        this->pr=pr;
        this->sz=1;
        this->l=l;
        this->r=r;
        }
}*r,*nil;
T* update(T *t)
{
    if (t==nil)
        return t;
    t->sz=1+t->l->sz+t->r->sz;
    return t;
}
pair<T*,T*> split(T *t,int p)
{
    pair<T*,T*>aux;
    t=update(t);
    if (t==nil)
        return make_pair(t,t);
    if (t->l->sz+1>p)
        {
        aux=split(t->l,p);
        t->l=aux.second;
        aux.second=t;
        }
    else
        {
        aux=split(t->r,p-(t->l->sz+1));
        t->r=aux.first;
        aux.first=t;
        }
    update(t);
    return aux;
}
T* join(T *lt,T *rt)
{
    lt=update(lt);
    rt=update(rt);
    if (lt==nil)
        return rt;
    if (rt==nil)
        return lt;
    if (lt->pr>rt->pr)
        {
        lt->r=join(lt->r,rt);
        lt=update(lt);
        return lt;
        }
    else
        {
        rt->l=join(lt,rt->l);
        rt=update(rt);
        return rt;
        }
}
T* insert(T *t,int p,int key,int pr)
{
    t=update(t);
    pair<T*,T*>aux;
    if (pr>t->pr)
        {
        aux=split(t,p);
        t=new T(key,pr,aux.first,aux.second);
        }
    else
        {
        if (t->l->sz+1>p)
            t->l=insert(t->l,p,key,pr);
        else
            t->r=insert(t->r,p-(t->l->sz+1),key,pr);
        }
    t=update(t);
    return t;
}
T* erase(T *t,int p)
{
    t=update(t);
    T *aux;
    if (t->l->sz+1==p)
        {
        aux=join(t->l,t->r);
        delete t;
        t=aux;
        }
    else
        {
        if (t->l->sz+1>p)
            t->l=erase(t->l,p);
        else
            t->r=erase(t->r,p-(t->l->sz+1));
        }
    t=update(t);
    return t;
}
T* rotate(T *t,int p)
{
    pair<T*,T*>aux=split(t,p);
    t=join(aux.second,aux.first);
    return t;
}
int find(T* t,int p)
{
    if (t==nil)
        return -1;
    if (t->l->sz+1==p)
        return t->key;
    if (t->l->sz+1>p)
        return find(t->l,p);
    else
        return find(t->r,p-(t->l->sz+1));
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    int n,i,p;
    scanf("%d",&n);
    srand(time(0));
    r=nil=new T;
    r->l=r->r=nil;
    for(i=1;i<=n;i++)
        r=insert(r,i,i,abs(rand())%INT_MAX);
    for(i=1;i<=n;i++)
        {
        p=(i-1)%(n-i+1)+1;
        if (i==1)
            p=2;
        r=rotate(r,p-1);
        printf("%d ",find(r,1));
        r=erase(r,1);
        }
return 0;
}