Pagini recente » Cod sursa (job #318624) | Cod sursa (job #2713235) | Cod sursa (job #3198079) | Cod sursa (job #2279895) | Cod sursa (job #1794620)
# include <iostream>
# include <fstream>
# include <cstdlib>
# include <cassert>
using namespace std;
struct Node
{
int value;
int priority;
int weight;
Node * left;
Node * right;
Node( int value )
{
this->value = value;
this->priority = rand();
this->weight = 1;
this->left = NULL;
this->right = NULL;
}
};
class Treap
{
public:
Treap();
void push( int pos, int x );
void print( ofstream &fout );
private:
Node * root;
void rotLeft( Node * &n );
void rotRight( Node * &n );
void balance( Node * &n );
void insert( Node * &n, int pos, int value );
void printNode( Node * &n, ofstream &fout );
int weight( Node * &n );
void updateWeight( Node * &n );
};
void Treap::updateWeight( Node * &n )
{
n->weight = 1 + weight( n->left ) + weight( n->right );
}
int 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, int pos, int 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( int pos, int x )
{
insert( root, pos - 1, x );
}
Treap::Treap()
{
srand( time( NULL ) );
root = NULL;
}
int main()
{
ifstream fin( "schi.in" );
ofstream fout( "schi.out" );
int 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;
}