Pagini recente » Cod sursa (job #990130) | Cod sursa (job #221941) | Cod sursa (job #750641) | Cod sursa (job #2366028) | Cod sursa (job #1806922)
#include <bits/stdc++.h>
using namespace std;
int i,n,nn,poz,q;
struct treap
{
int val, prior, cate;
treap *left, *right;
treap(){}
treap(int val, int prior, treap *left, treap *right)
{
int ll,rr;
this->val=val;
this->prior=prior;
this->left=left;
this->right=right;
cate=0;
}
};
treap *rad, *nil;
void init(treap *&rad)
{
srand(unsigned(time(0)));
rad=nil=new treap(0,0,NULL,NULL);
}
void update_cate(treap *&nod)
{
if(nod==nil);
else nod->cate=nod->left->cate+nod->right->cate+1;
}
int cauta(treap *nod, int nr)
{
if(nod->left->cate<nr)
{
nr=nr-(nod->left->cate);
if(nr==1) return nod->val;
else return cauta(nod->right,nr-1);
}
else return cauta(nod->left,nr);
}
void rot_left(treap *&nod)
{
treap *t=nod->left;
nod->left=t->right;
t->right=nod;
nod=t;
update_cate(nod);
}
void rot_right(treap *&nod)
{
treap *t=nod->right;
nod->right=t->left;
t->left=nod;
nod=t;
update_cate(nod);
}
void balance(treap *&nod)
{
if(nod->left->prior > nod->prior)rot_left(nod);
else if (nod->right->prior > nod->prior)rot_right(nod);
update_cate(nod);
}
void inserare(treap *&nod, int val, int prior)
{
if(nod==nil)
{
nod=new treap(val,prior,nil,nil);
return;
}
if(val < nod->val)inserare(nod->left, val, prior);
else if (val > nod->val)inserare(nod->right, val, prior);
balance(nod);
}
void stergere(treap *&nod, int val)
{
if(nod==nil)return;
if(val < nod->val)stergere(nod->left, val);
else if(val > nod->val)stergere(nod->right, val);
else
{
if(nod->left==nil&&nod->right==nil)
{
delete nod;
nod=nil;
}
else
{
if(nod->left->prior > nod->right->prior)rot_left(nod);
else rot_right(nod);
stergere(nod, val);
}
}
update_cate(nod);
}
int main()
{
freopen("order.in","r",stdin);
freopen("order.out","w",stdout);
init (rad);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
inserare(rad,i,rand()+1);
}
nn=n;
poz=1;
for(i=1;i<=n;i++)
{
poz=poz+i;
poz=poz%nn;
if(poz==0)poz=nn;
nn--;
q=cauta(rad,poz);
printf("%d ",q);
stergere(rad,q);
}
return 0;
}