Pagini recente » Cod sursa (job #2821432) | Cod sursa (job #1494285) | Cod sursa (job #709419) | Cod sursa (job #2988422) | Cod sursa (job #392199)
Cod sursa(job #392199)
#include <stdio.h>
#include <ctime>
#include <stdlib.h>
struct nod
{
int val,s,p;
nod *st,*dr;
};
int n,i,poz,pas;
nod *t,*u,*aux;
int rangs(nod *treap)
{
if (treap->st==NULL)
return 0;
return treap->st->s;
}
int rangd(nod *treap)
{
if (treap->dr==NULL)
return 0;
return treap->dr->s;
}
int ps(nod *treap)
{
if (treap->st==NULL)
return 0;
return treap->st->p;
}
int pd(nod *treap)
{
if (treap->dr==NULL)
return 0;
return treap->dr->p;
}
void rotleft(nod *&treap)
{
u=treap->st;
treap->st=u->dr;
u->dr=treap;
u->s=rangs(u)+rangs(treap)+rangd(treap)+2;
treap->s=rangs(treap)+rangd(treap)+1;
treap=u;
}
void rotright(nod *&treap)
{
u=treap->dr;
treap->dr=u->st;
u->st=treap;
u->s=rangd(u)+rangs(treap)+rangd(treap)+2;
treap->s=rangs(treap)+rangd(treap)+1;
treap=u;
}
void balance(nod *&treap)
{
if (treap->st!=NULL && treap->st->p>treap->p)
rotleft(treap);
else
if (treap->dr!=NULL && treap->dr->p>treap->p)
rotright(treap);
}
void insert(nod *&treap,int val,int poz,int p)
{
if (treap==NULL)
{
treap=new nod;
treap->val=val;
treap->s=0;
treap->p=p;
treap->st=NULL,treap->dr=NULL;
}
else
if (poz<=rangs(treap))
insert(treap->st,val,poz,p);
else
insert(treap->dr,val,poz-rangs(treap)-1,p);
++treap->s;
balance(treap);
}
void sterge(nod *&treap)
{
if (treap->st==NULL && treap->dr==NULL)
delete treap,treap=NULL;
else
{
if (ps(treap)>pd(treap))
{
rotleft(treap);
sterge(treap->dr);
}
else
{
rotright(treap);
sterge(treap->st);
}
--treap->s;
}
}
int access(nod *&treap,int poz)
{
int ret;
if (poz<=rangs(treap))
ret=access(treap->st,poz);
else
if (poz>rangs(treap)+1)
ret=access(treap->dr,poz-rangs(treap)-1);
else
{
ret=treap->val;
sterge(treap);
return ret;
}
--treap->s;
return ret;
}
int main()
{
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
scanf("%d",&n);
srand(unsigned(time(0)));
for (i=1;i<=n;++i)
insert(t,i,i,rand()+1);
poz=2;
do
{
printf("%d ",access(t,poz));
++pas;
--n;
if (!n)
break;
poz=(poz+pas)%n;
if (!poz)
poz=n;
}
while (n);
return 0;
}