Pagini recente » Cod sursa (job #3189428) | Cod sursa (job #1894290) | Cod sursa (job #2903227) | Cod sursa (job #197042) | Cod sursa (job #399014)
Cod sursa(job #399014)
#include <cstdio>
#include <string>
#include <cstdlib>
#define oo 0x3f3f3f3f
struct nod { int v, p, h; nod *l, *r;};
nod *R,*nil;
typedef nod* treap; //treapul asigura O(logn) pt insert, delete, find
inline void init()
{
srand(time(0));
nil=new nod;
nil->v=nil->p=-oo;
nil->h=0;
nil->l=nil->r=nil;
R=nil;
}
inline void geth(treap &n)
{
if(n==nil)return;
n->h=1;
if(n->l) n->h += n->l->h;
if(n->r) n->h += n->r->h;
}
inline void rotleft(treap &n)
{
treap t=n->l; n->l=t->r; t->r=n;geth(n); geth(t); n=t;
}
inline void rotright(treap &n)
{
treap t=n->r; n->r=t->l; t->l=n; geth(n); geth(t); n=t;
}
inline void insrt(treap &n, int v)
{
if(n==nil)
{
n=new nod;
n->v=v; n->p=rand()-1; n->h=1; n->l=n->r=nil;
return ;
}
if(v<n->v)
{
insrt(n->l, v);
if(n->l->p > n->p) rotleft(n);
}
if(v>n->v)
{
insrt(n->r, v);
if(n->r->p > n->p) rotright(n);
}
geth(n);
}
inline void sterge(treap &n, int v)
{
if(n==nil) return;
if(v<n->v) sterge(n->l, v);
if(v>n->v) sterge(n->r, v);
if(v==n->v)
{
if(n->l->p > n->r->p) rotleft(n);
else rotright(n);
if(n!=nil) sterge(n, v);
else
{
free(n->l);
n->l=0;
}
}
geth(n);
}
void ino(treap n)
{
if(n==nil) return;
ino(n->l);
printf("(%d %d) ", n->v, n->h);
ino(n->r);
}
inline int findk(treap n, int k)
{
if(n==nil) return 0;
if(k==n->l->h+1) return n->v;
if(k<n->l->h+1) return findk(n->l, k);
else return findk(n->r, k-(n->l->h+1));
return 0;
}
inline void del(int v)
{
sterge(R, v);
}
inline void insert(int v)
{
insrt(R, v);
}
int main()
{
init();
int i,n, K, p=1, found;
//se citesc n si K
//n=100000; K=100000;
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
scanf("%d", &n);
for(i=1;i<=n;++i)insert(i);
i=1;
K=1;
while(n)
{
p=(p+K-1)%n+1;
K++;
found=findk(R, p);
printf("%d ", found);
del(found);
p--;
++i;
--n;
}
return 0;
}