Cod sursa(job #1399148)

Utilizator danalex97Dan H Alexandru danalex97 Data 24 martie 2015 16:30:09
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

struct item {
    short int sz,vl;
    int pr;
    item *l , *r;
    item() {
    }
    item(short vl)
    {
        this->vl = vl;
        l = r = NULL;
        pr = (rand() << 6) ^ rand();
        sz = 1;
    }
};

#define tree item*

void compute(tree &t)
{
    if ( t == NULL ) return;
    t->sz = 1;
    t->sz += t->l ? t->l->sz : 0;
    t->sz += t->r ? t->r->sz : 0;
}

void split(tree t,int pl,tree &l,tree &r)
{
    if ( t == NULL )
    {
        l = r = NULL;
        return;
    }
    int sl = t->l ? t->l->sz : 0;
    if ( pl <= sl )
    {
        split(t->l,pl,l,t->l); // tai la pl
        r = t;
    }
    else
    {
        split(t->r,pl-sl-1,t->r,r); // tai la pl-sl-1
        l = t;
    }
    compute(l);
    compute(r);
}

void insert(tree &t,int pl,tree x)
{
    int sl = t ? t->l ? t->l->sz : 0 : 0;
    if ( !t )
        t = x;
    else
        if ( t->pr > x->pr )
        {
            split(t,pl,x->l,x->r);
            t = x;
        }
        else
        {
            if ( pl <= sl )
                insert(t->l,pl,x);
            else
                insert(t->r,pl-sl-1,x);
        }
    compute(t);
}

void print(tree t)
{
    if ( t->l )
        print(t->l);
    printf("%d\n",t->vl);
    if ( t->r )
        print(t->r);
}

int n;
tree t = NULL;

int main()
{
    srand(time(0));

    freopen("schi.in","r",stdin);
    freopen("schi.out","w",stdout);

    scanf("%d\n",&n);
    for (int i=1,p;i<=n;++i)
    {
        scanf("%d",&p);
        tree x = new item(i);
        insert(t,p-1,x);
    }
    print(t);
}