Pagini recente » Cod sursa (job #1159412) | Cod sursa (job #2760516) | Cod sursa (job #564473) | Cod sursa (job #419816) | Cod sursa (job #2342729)
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
ifstream fin( "order.in" );
ofstream fout( "order.out" );
struct Treap;
Treap* NIL;
typedef pair<Treap*,Treap*> Trip;
struct Treap
{
int k, p, size;
Treap *st, *dr;
Treap( int val, int pr=rand() )
{
k=val;
p=pr;
size=1;
st=NIL, dr=NIL;
}
void resize( )
{
size=st->size+dr->size+1;
}
};
Treap* join( Treap* a, Treap* b )
{
if( a==NIL )
return b;
if( b==NIL )
return a;
if( a->p>b->p )
{
a->dr=join(a->dr,b);
a->resize();
return a;
}
else
{
b->st=join(a,b->st);
b->resize();
return b;
}
}
Trip split( Treap* x, int pos )
{
if( x==NIL )
return Trip{NIL,NIL};
if( pos<=x->st->size )
{
Trip t=split(x->st,pos);
x->st=t.second;
x->resize();
return Trip{t.first,x};
}
else
{
Trip t=split(x->dr,pos-x->st->size-1);
x->dr=t.first;
x->resize();
return Trip{x,t.second};
}
}
int access( Treap* x, int pos )
{
if( pos<=x->st->size )
return access(x->st,pos);
if( pos>x->st->size+1 )
return access(x->dr,pos-x->st->size-1);
return x->k;
}
void displayTreap(Treap *root, int space = 0) {
for(int i = 0; i < space; ++i)
fout<<" ";
fout<<"INFO: "<<root->k<<" "<<root->p<<"{\n";
if( root->st!=NIL )
displayTreap(root->st,space+2);
if( root->dr!=NIL )
displayTreap(root->dr,space+2);
for(int i = 0; i < space; ++i)
fout << " ";
fout<<"}\n";
}
int main()
{
int n;
fin>>n;
NIL=new Treap(-1);
NIL->p=-1;
NIL->size=0;
NIL->st=NIL->dr=NIL;
Treap* root=NIL;
for( int i=1;i<=n;i++ )
root=join(root,new Treap(i,i));
int poz=1;
for( int i=1;i<n;i++ )
{
poz=(poz+i-1)%(n-i+1)+1;
fout<<access(root,poz)<<" ";
Trip t1=split(root,poz-1);
Trip t2=split(t1.second,1);
root=join(t1.first,t2.second);
poz--;
}
fout<<access(root,1);
return 0;
}