Cod sursa(job #1275485)

Utilizator sebinechitasebi nechita sebinechita Data 25 noiembrie 2014 11:41:49
Problema Schi Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fin("schi.in");
ofstream fout("schi.out");

struct T{
    int key, priority, s, value;
    T *left, *right;

    void update()
    {
        this->s=1;
        if(this->left)
            this->s+=this->left->s;
        if(this->right)
            this->s+=this->right->s;
    }
    T(int k, int p, T* l, T* r, int va)
    {
        s = 0;
        this->priority = p;
        this->key = k;
        this->left = l;
        this->right = r;
        this->value = va;
    }
} *R, *nil;

void init()
{
    srand(time(0));
    R = nil = new T(0, 0, 0, 0, 0);
}

void rotL(T* &n)
{
    T* x = n->left;
    n->left = x->right;
    x->right = n;
    n->update();
    n = x;
    n->update();
}

void rotR(T* &n)
{
    T* x = n->right;
    n->right = x->left;
    x->left = n;
    n->update();
    n = x;
    n->update();
}

void balance(T* &n)
{
    if(n->left->priority > n->priority)
        rotL(n);
    else if(n->right->priority > n->priority)
        rotR(n);
}

void put(T* &n, int key, int priority, int value)
{
    if(n == nil)
    {
        n = new T(key, priority, nil, nil, value);
        n->update();
        return;
    }
    put(n->right, key, priority, value);
    n->update();
}

void insert(T* &n, int key, int priority, int value)
{
    if(n == nil)
    {
        put(n, key, priority, value);
    }
    else if(n->left->s >= value)
    {
        insert(n->left, key, priority, value);
        n->update();
    }
    else if(n->left->s + 1 == value)
    {
        put(n->left, key, priority, value);
        n->update();
    }
    else
    {

        insert(n->right, key, priority, value-(n->left->s+1));
        n->update();
    }
}

void af(T* &n)
{
    if(n == nil)
        return;
    af(n->left);
    fout << n->key << "\n";
    af(n->right);
}

int main()
{
    int n, i, x;
    init();
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>x;
        insert(R, i, rand()+1, x);
    }
    af(R);

}