Cod sursa(job #1399092)

Utilizator danalex97Dan H Alexandru danalex97 Data 24 martie 2015 16:07:14
Problema Schi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

ifstream F("schi.in");
ofstream G("schi.out");

struct item {
    int sz,vl,pr;
    item *l , *r;
    item() {
    }
    item(int vl)
    {
        this->vl = vl;
        l = r = NULL;
        pr = (rand() << 16) ^ 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-1,l,t->l); // tai la pl-1
        r = t;
    }
    else
    {
        split(t->r,pl-sl-1,t->r,r); // tap 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);
    G<<t->vl<<'\n';
    if ( t->r )
        print(t->r);
}

void printd(tree t)
{
    if ( t->l )
        printd(t->l);
    cerr<<t->vl<<' ';
    if ( t->r )
        printd(t->r);
}

int n;
tree t = NULL;

int main()
{
    srand(time(0));
    F>>n;
    for (int i=1,p;i<=n;++i)
    {
        F>>p;
        tree x = new item(i);
        insert(t,p-1,x);
        printd(t); cerr<<'\n';
    }
    print(t);
}