Pagini recente » Cod sursa (job #258858) | Cod sursa (job #81226) | Cod sursa (job #238899) | Cod sursa (job #1512312) | Cod sursa (job #1175975)
#include <algorithm>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
struct Treap {
int key, pry, size;
Treap *left, *right;
Treap() {}
Treap(const int _key, const int _pry, const int _size, Treap *_left, Treap *_right)
{
key=_key;
pry=_pry;
size=_size;
left=_left;
right=_right;
}
};
Treap *Root, *NIL;
void Update(Treap* &node)
{
node->size=node->left->size+node->right->size+1;
}
void RotLeft(Treap* &node)
{
Treap *t=node->left;
node->left=t->right;
t->right=node;
node=t;
Update(node->right);
Update(node);
}
void RotRight(Treap* &node)
{
Treap *t=node->right;
node->right=t->left;
t->left=node;
node=t;
Update(node->left);
Update(node);
}
int get_rand()
{
int ret=(rand()%32768)*10000+rand()%32768;
if(ret<0) ret=-ret;
if(!ret) ret++;
return ret;
}
void Balance(Treap* &node)
{
if(node->left->pry>node->pry) RotLeft(node);
else if(node->right->pry>node->pry) RotRight(node);
}
void Insert(Treap* &node, int key, int pry)
{
if(node==NIL)
{
node=new Treap(key, pry, 1, NIL, NIL);
return;
}
if(key<node->key) Insert(node->left, key, pry);
else if(key>node->key) Insert(node->right, key, pry);
Update(node);
Balance(node);
}
int NthElement(Treap* &node, int poz)
{
if(node->left->size>=poz) return NthElement(node->left, poz);
if(node->left->size+1==poz) return node->key;
return NthElement(node->right, poz-node->left->size-1);
}
void Erase(Treap* &node, int key)
{
if(node==NIL) return;
if(node->key==key)
{
if(node->left==NIL&&node->right==NIL)
{
delete node;
node=NIL;
return;
}
if(node->left->pry>node->right->pry) RotLeft(node);
else RotRight(node);
Erase(node, key);
}
else if(key<node->key) Erase(node->left, key);
else Erase(node->right, key);
Update(node);
}
void Init()
{
srand(time(0));
Root=NIL=new Treap(0, 0, 0, NULL, NULL);
}
int main()
{
Init();
int N;
fin>>N;
for(int i=1;i<=N;i++) Insert(Root, i, get_rand());
for(int i=1, j=0;i<=N;i++)
{
j=(j+i)%(N-i+1);
int x=NthElement(Root, j+1);
fout<<x<<" ";
Erase(Root, x);
j--;
}
fout<<"\n";
fin.close();
fout.close();
}