Pagini recente » Cod sursa (job #2944156) | Cod sursa (job #1973710) | Cod sursa (job #282707) | Cod sursa (job #1491386) | Cod sursa (job #1978241)
#include <fstream>
using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int n;
struct treap{
int key,pr,nr;
treap *st,*dr;
treap(int _key, int _pr, treap *_st, treap *_dr) : key(_key) , pr(_pr) , st(_st) , dr(_dr) , nr(0){};
}*T,*nil;
void right(treap *&t)
{
treap *x = t->st;
t->st = x->dr;
x->dr = t;
t = x;
t->dr->nr = t->dr->st->nr + t->dr->dr->nr + 1;
t->nr = t->st->nr + t->dr->nr +1;
}
void left(treap *&t)
{
treap *x = t->dr;
t->dr = x->st;
x->st = t;
t = x;
t->st->nr = t->st->st->nr + t->st->dr->nr + 1;
t->nr = t->st->nr + t->dr->nr +1;
}
void balance(treap *&t)
{
if(t->st->pr > t->pr)
right(t);
else if (t->dr->pr > t->pr)
left(t);
}
void add(treap *&t,int key,int pr)
{
if (t == nill)
{
t->st = nill;
t->dr = nill;
t->key = key;
t->pr = pr;
t->nr = 1;
}
else if (t->key > key)
{
t->nr++;
add(t->st,key,pr);
}
else if (t->key < key)
{
t->nr++;
add(t->dr,key,pr);
}
balance(t);
}
int _find(treap *&t,int x)
{
if (t->st->nr+1==x)
return t->key;
else if (t->st->nr>x)
return _find(t->st,x);
else
return _find(t->dr,x);
}
void dell(treap *&t,int key)
{
treap *l,*r;
split(t,key,l,r);
}
int main()
{
srand(time(0));
f>>n;
T = nil = new treap (0,0,NULL,NULL);
for (int i=1;i<=n;i++)
add(T,i,rand()+1);
int nr = n;
for (i=1;i<=n;i++)
{
int x = i%nr;
if (x==0)
x = nr;
g<<_find(T,x);
dell(T,_find(T,x));
}
return 0;
}