Cod sursa(job #1668535)

Utilizator sebinechitasebi nechita sebinechita Data 29 martie 2016 20:58:38
Problema Schi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");

struct treap{
    int ind, s;
    int priority;
    treap *l, *r;
    treap(int i, int p, treap *le, treap *ri)
    {
        ind = i;
        priority = p;
        l = le;
        r = ri;
        s = 0;
    }
} *R, *nil;

void init()
{
    R = nil = new treap(0, 0, 0, 0);
}

void update(treap *&R)
{
    R->s = R->l->s + R->r->s + 1;
}

void Rleft(treap* &R)
{
    treap *p = R->l;
    R->l = p->r;
    p->r = R;
    update(R);
    R = p;
    update(R);
}

void Rright(treap* &R)
{
    treap *p = R->r;
    R->r = p->l;
    p->l = R;
    update(R);
    R = p;
    update(R);
}

void balance(treap* &R)
{
    if(R->l->priority > R->priority)
        Rleft(R);
    else if(R->r->priority > R->priority)
        Rright(R);
}

void insereaza(treap *&R, double x, int i)
{
    if(R == nil)
    {
        R = new treap(i, rand() + 1, nil, nil);
        update(R);
        return;
    }
    if(1.0 * R->l->s + 1 > x)
    {
        insereaza(R->l, x, i);
    }
    else
    {
        insereaza(R->r, x - R->l->s - 1, i);
    }
    update(R);
    balance(R);
}

void df(treap *R)
{
    if(R == nil)
        return;
    df(R->l);
    fout << R->ind << "\n";
    df(R->r);
}

int main()
{
    int n, i, x;
    init();
    fin >> n;
    for(i = 1 ; i <= n ; i++)
    {
        fin >> x;
        insereaza(R, 1.0 * x - 0.5, i);
    }
    df(R);
}