Cod sursa(job #1438259)

Utilizator danalex97Dan H Alexandru danalex97 Data 19 mai 2015 15:10:43
Problema Schi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;

/// To be submited

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

struct item {
    int pr,vl,sz;
    item *l,*r;

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

#define cart item*

void upd(cart &t)
{
    return !t ? void() : void( t->sz = ( t->l ? t->l->sz : 0 ) + ( t->r ? t->r->sz : 0 ) + 1 );
}

void split(cart t,int pl,cart &l,cart &r)
{
    if ( !t )
        return void(l = r = NULL);
    int sz = t->l ? t->l->sz : 0;
    if ( pl <= sz )
        split(t->l,pl,l,t->l) , r = t;
    else
        split(t->r,pl-sz-1,t->r,r) , l = t;
    upd(l);
    upd(r);
}

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

void print(cart x)
{
    if ( x->l ) print(x->l);
    G<<x->vl<<'\n';
    if ( x->r ) print(x->r);
}

void inline_print(cart x)
{
    if ( x->l ) inline_print(x->l);
    cerr<<x->vl<<' ';
    if ( x->r ) inline_print(x->r);
}

int n;

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

    F>>n;
    cart t = NULL;

    for (int i=1,p;i<=n;++i)
    {
        F>>p;
        cart x = new item(i);
        insert(t,p-1,x);
        //inline_print(t); cerr<<'\n';
    }
    print(t);
}