Pagini recente » Cod sursa (job #1208750) | Cod sursa (job #1584528) | Cod sursa (job #1715813) | Cod sursa (job #1451532) | Cod sursa (job #245104)
Cod sursa(job #245104)
#include<stdio.h>
#include<stdlib.h>
#include<ctime>
FILE *f=fopen("order.in","r"), *g=fopen("order.out","w");
struct nod { int v,p, nrnodes; nod *l,*r;};
typedef nod* treap;
treap R,nil;
int n,i,q,k,p;
inline void init()
{
nil=new nod;
nil->l=nil->r=0;
nil->v=nil->p=-0x3f3f3f3f;
nil->nrnodes=0;
R=nil;
}
inline void geth(treap &n)
{
if(n == nil) return;
n->nrnodes=n->l->nrnodes + n->r->nrnodes +1;
}
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 insert(treap &n, int v)
{
if(n == nil)
{
n=new nod;
n->l=n->r=nil;
n->v=v;
n->nrnodes=1;
n->p=rand();
return ;
}
if(v < n->v)
{
insert(n->l, v);
if(n->l->p > n->p) rotleft(n);
}
if(v > n->v)
{
insert(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 == nil && n->r == nil)
{
delete n;
n=nil;
return;
}
if(n->l->p > n->r->p) rotleft(n);
else rotright(n);
sterge(n, v);
}
geth(n);
}
inline int findk(treap n, int k)
{
if(n == nil) return 0;
if(n->l->nrnodes + 1 == k) return n->v;
if(n->l->nrnodes + 1 > k) return findk(n->l, k);
else return findk(n->r, k - (n->l->nrnodes+1));
return 0;
}
int main()
{
fscanf(f,"%d",&n);
fclose(f);
init();
for(i=1;i<=n;i++) insert(R,i);
p=1;
i=1;
k=1;
while(n)
{
p+=k;
p%=n;
if(i!=1) p--;
if(p==-1) p=n-1;
if(p==0) p=n;
k++;
q=findk(R,p);
fprintf(g,"%d ",q);
sterge(R,q);
++i;
n--;
}
fprintf(g,"\n");
fclose(g);
return 0;
}