Cod sursa(job #1794624)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 1 noiembrie 2016 15:53:28
Problema Schi Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
# include <iostream>
# include <fstream>

# include <cstdlib>
# include <cassert>

using namespace std;

struct Node
{
    short value;
    short priority;
    short weight;
    Node * left;
    Node * right;

    Node( short value )
    {
        this->value = value;
        this->priority = rand();
        this->weight = 1;
        this->left = NULL;
        this->right = NULL;
    }
};

class Treap
{
public:
    Treap();
    void push( short pos, short x );
    void print( ofstream &fout );

private:
    Node * root;
    void rotLeft( Node * &n );
    void rotRight( Node * &n );
    void balance( Node * &n );
    void insert( Node * &n, short pos, short value );
    void printNode( Node * &n, ofstream &fout );
    short weight( Node * &n );
    void updateWeight( Node * &n );
};

void Treap::updateWeight( Node * &n )
{
    n->weight = 1 + weight( n->left ) + weight( n->right );
}

short Treap::weight( Node * &n )
{
    return ( n == NULL ? 0 : n->weight );
}

void Treap::printNode( Node * &n, ofstream &fout )
{
    if ( n == NULL )
        return;

    printNode( n->left, fout );
    fout << n->value << '\n';
    printNode( n->right, fout );
}

void Treap::insert( Node * &n, short pos, short value )
{
    if ( n == NULL ) {
        assert( pos == 0 );
        n = new Node( value );
    } else if ( pos <= weight( n->left ) )
        insert( n->left, pos, value );
    else
        insert( n->right, pos - weight( n->left ) - 1, value );

    updateWeight( n );
    balance( n );
}

void Treap::balance( Node * &n )
{
    if ( n == NULL )
        return;

    if ( n->left != NULL && n->left->priority > n->priority )
        rotLeft( n );
    if ( n->right != NULL && n->right->priority > n->priority )
        rotRight( n );
}

void Treap::rotRight( Node * &n )
{
    Node * t = n->right;
    n->right = t->left;
    t->left = n;
    n = t;

    updateWeight( n->left );
    updateWeight( n );
}

void Treap::rotLeft( Node * &n )
{
    Node * t = n->left;
    n->left = t->right;
    t->right = n;
    n = t;

    updateWeight( n->right );
    updateWeight( n );
}

void Treap::print( ofstream &fout )
{
    printNode( root, fout );
}

void Treap::push( short pos, short x )
{
    insert( root, pos - 1, x );
}

Treap::Treap()
{
    srand( time( NULL ) );
    root = NULL;
}

int main()
{
    ifstream fin( "schi.in" );
    ofstream fout( "schi.out" );

    short n, i, p;
    Treap clasament;

    fin >> n;

    for ( i = 1; i <= n; i ++ ) {
        fin >> p;
        clasament.push( p, i );
    }

    clasament.print( fout );

    fin.close();
    fout.close();

    return 0;
}