Cod sursa(job #1791838)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 29 octombrie 2016 19:32:30
Problema Order Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.93 kb
# include <iostream>
# include <fstream>

using namespace std;

struct Node
{
    int key, priority;
    int weight;

    Node * left, * right;

    Node( int _key, int _priority = -1, Node * _left = NULL, Node * _right = NULL )
    {
        key = _key;
        priority = ( _priority == -1 ? rand() : _priority );
        left = _left;
        right = _right;

        int l = ( left == NULL ? 0 : left->weight );
        int r = ( right == NULL ? 0 : right->weight );

        weight = l + 1 + r;
    }
};

class Treap
{
public:
    Treap( void );
    void push( int x );
    void pop( int x );
    int kth( int k );
    int size( void );
    void print( void );

private:
    Node * root;
    void insert( Node * &n, int key, int priority );
    void erase( Node * &n, int key );
    int ktht( Node * &n, int k );
    void rotLeft( Node * &n );
    void rotRight( Node * &n );
    void balance( Node * &n );
    void updateWeight( Node * &n );
    void printn( Node * &n );
};

void Treap::printn( Node * &n )
{
    if ( n == NULL )
        return;
    cout << n->key << ':' << n->weight << ' ';
    printn( n->left );
    printn( n->right );
}

void Treap::print( void )
{
    printn( root );
    cout << endl;
}

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

    int l = ( n->left == NULL ? 0 : n->left->weight );
    int r = ( n->right == NULL ? 0 : n->right->weight );

    n->weight = l + 1 + r;
}

int Treap::ktht( Node * &n, int k )
{
    int l = ( n->left == NULL ? 0 : n->left->weight );

    if ( k <= l )
        return ktht( n->left, k );
    else if ( k == l + 1 )
        return n->key;
    else
        return ktht( n->right, k - 1 - l );
}

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

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

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

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

void Treap::balance( Node * &n )
{
    if ( n == NULL || n->left == NULL && n->right == NULL )
        return;

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

    updateWeight( n );
}

void Treap::erase( Node * &n, int key )
{
    if ( n == NULL )
        return;

    if ( key < n->key )
        erase( n->left, key );
    else if ( key > n->key )
        erase( n->right, key );
    else {
        if ( n->left == NULL && n->right == NULL ) {
            delete n;
            n = NULL;
        } else {
            if ( n->left == NULL || n->right != NULL &&
                 n->right->priority > n->left->priority ) {
                rotRight( n );
                erase( n, key );
            } else {
                rotLeft( n );
                erase( n, key );
            }
        }
    }

    updateWeight( n );
}

void Treap::insert( Node * &n, int key, int priority )
{
    if ( n == NULL )
        n = new Node( key, priority );
    else if ( key <= n->key )
        insert( n->left, key, priority );
    else
        insert( n->right, key, priority );

    balance( n );
    updateWeight( n );
}

int Treap::size( void )
{
    return ( root == NULL ? 0 : root->weight );
}

int Treap::kth( int k )
{
    return ktht( root, k );
}

void Treap::pop( int x )
{
    erase( root, x );
}

void Treap::push( int x )
{
    insert( root, x, rand() );
}

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

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

    int n, i, p, t;
    Treap circle;

    fin >> n;

    for ( i = 1; i <= n; i ++ ) {
        circle.push( i );
    }

    p = 2;
    for ( i = 1; i <= n; i ++ ) {
        p = ( p - 2 + i ) % circle.size() + 1;
        t = circle.kth( p );
        circle.pop( t );
        fout << t << ' ';
    }

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

    return 0;
}