Pagini recente » Borderou de evaluare (job #2557141) | Cod sursa (job #2562434) | Cod sursa (job #1978301)
#include <fstream>
#include <cstdlib>
#include <ctime>
#define inf 1e9
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 == nil)
{
t = new treap(key,pr,nil,nil);
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)
{
if(t == nil)
return;
if(t->key > key)
dell(t->st,key);
else if(t->key<key)
dell(t->dr,key);
else
{
if (t->st == NULL && t->dr==NULL)
{
delete t;
t = nil;
}
else
{
if (t->st->pr > t->dr->pr)
right(t);
else
left(t);
dell(t,key);
}
}
}
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,x = 1;
for (int i=1;i<=n;i++)
{
x = (x+i)%nr;
if (x==0)
x = nr;
g<<_find(T,x)<<'\n';
dell(T,_find(T,x));
nr--;
}
return 0;
}