Cod sursa(job #1694503)

Utilizator DysKodeTurturica Razvan DysKode Data 25 aprilie 2016 15:36:39
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <cstdlib>
#include <ctime>

using namespace std;

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

struct Treap
{
    int key,pri,cnt;
    Treap *left,*right;
    Treap( int k, int p, int c, Treap *l, Treap *r )
    {
        key = k;
        pri = p;
        cnt = c;
        left = l;
        right = r;
    }
}*R,*G;

void recalc( Treap *&n )
{
    if( n != G )
        n -> cnt = 1 + n -> left -> cnt + n -> right -> cnt;
}

void rotateLeft( Treap *&n )
{
    Treap *t = n -> left;
    n -> left = t -> right;
    t -> right = n;
    recalc( n );
    recalc( t );
    n = t;
}

void rotateRight( Treap *&n )
{
    Treap *t = n -> right;
    n -> right = t -> left;
    t -> left = n;
    recalc( n );
    recalc( t );
    n = t;
}

void balance( Treap *&n )
{
    if( n -> left -> pri > n -> pri )
        rotateLeft( n );
    else if( n -> right -> pri > n -> pri )
        rotateRight( n );
    recalc( n );
}

void addNode( Treap *&n, int k, int p )
{
    if( n == G )
    {
        n = new Treap( k , p , 1 , G , G );
        return;
    }
    if( n -> key == k )
        return;
    else if( n -> key > k )
        addNode( n -> left , k , p );
    else
        addNode( n -> right , k , p );
    balance( n );
}

void removeNode( Treap *&n, int k )
{
    if( n == G )
        return;
    else if( n -> key == k )
    {
        if( n -> left == G && n -> right == G )
        {
            delete n;
            n = G;
            return;
        }
        else
        {
            if( n -> left -> pri > n -> right -> pri )
                rotateLeft( n );
            else
                rotateRight( n );
            removeNode( n , k );
        }
    }
    else if( n -> key > k )
        removeNode( n -> left , k );
    else
        removeNode( n -> right , k );
    recalc( n );
}

int go( Treap *n, int k )
{
    if( n -> left -> cnt + 1 == k )
        return n -> key;
    else if( n -> left -> cnt >= k )
        return go( n -> left , k );
    else
        return go( n -> right , k - n -> left -> cnt - 1 );
}

void afis( Treap *n )
{
    if( n == G )
        return;
    afis( n -> left );
    fout<<n -> key<<' ';
    afis( n -> right );
}

int n,i,k,o,p;

int main()
{
    srand( time( 0 ) );
    R = G = new Treap( 0 , 0 , 0 , 0 , 0 );
    fin>>n;
    for( i = 1 ; i <= n ; i++ )
        addNode( R , i , rand() + 1 );

    k = 1;
    for( i = 1 ; i <= n ; i++ )
    {
         k += i;
         k = k % ( n - i + 1 );
         if( k == 0 ) k = n - i + 1;
         o = go( R , k );
         fout<<o<<' ';
         removeNode( R , o );
         k--;
    }
return 0;
}