Pagini recente » Cod sursa (job #1155064) | Cod sursa (job #1663784) | Cod sursa (job #1768098) | Cod sursa (job #1736246) | Cod sursa (job #1791838)
# 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;
}