Pagini recente » Cod sursa (job #1408566) | Cod sursa (job #2485898) | Cod sursa (job #1145745) | Cod sursa (job #1844761) | Cod sursa (job #1694503)
#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;
}