Pagini recente » Cod sursa (job #1480790) | Cod sursa (job #2350522) | Cod sursa (job #2299552) | Cod sursa (job #1667554) | Cod sursa (job #1955367)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int i, n, k, ans;
int MyRand()
{
int x = rand();
return max(x, -x) + 5;
}
struct Treap
{
int key, prio, cnt;
Treap *left, *right;
Treap(int _key, int _prio, int _cnt, Treap *_left, Treap *_right)
{
key = _key, prio = _prio, cnt = _cnt, left = _left, right = _right;
}
} *root, *nul;
void rotate_left(Treap *& b)
{
Treap *a = b->left;
b->left = a->right;
a->right = b;
b = a;
int s = 0;
if(b->right->left) s += b->right->left->cnt;
if(b->right->right) s += b->right->right->cnt;
b->right->cnt = s + 1;
s = 0;
if(b->left) s += b->left->cnt;
if(b->right) s += b->right->cnt;
b->cnt = s + 1;
}
void rotate_right(Treap *& b)
{
Treap *a = b->right;
b->right = a->left;
a->left = b;
b = a;
int s = 0;
if(b->left->left) s += b->left->left->cnt;
if(b->left->right) s += b->left->right->cnt;
b->left->cnt = s + 1;
s = 0;
if(b->left) s += b->left->cnt;
if(b->right) s += b->right->cnt;
b->cnt = s + 1;
}
void balance(Treap *& t)
{
if(t->left->prio > t->prio) rotate_left(t);
else if(t->right->prio > t->prio) rotate_right(t);
}
int query(Treap *t, int k)
{
if(t->left->cnt == k-1) return t->key;
if(t->left->cnt >= k) return query(t->left, k);
return query(t->right, k - t->left->cnt - 1);
}
void add(Treap *&t, int Key)
{
if(t == nul)
{
t = new Treap(Key, MyRand(), 1, nul, nul);
return;
}
if(Key <= t->key) add(t->left, Key);
else add(t->right, Key);
balance(t);
t->cnt = t->left->cnt + t->right->cnt + 1;
}
void del(Treap *&t, int Key)
{
if(t->key == Key)
{
if(t->left == nul && t->right == nul)
{
delete t;
t = nul;
return;
}
if(t->left->prio > t->right->prio)
{
rotate_left(t);
del(t->right, Key);
}
else
{
rotate_right(t);
del(t->left, Key);
}
}
else if(Key <= t->key) del(t->left, Key);
else del(t->right, Key);
t->cnt = t->left->cnt + t->right->cnt + 1;
}
int main()
{
srand(time(0));
nul = new Treap(0, 0, 0, NULL, NULL);
root = new Treap(0, 1, 1, nul, nul);
fin >> n;
for(i=1; i<=n; ++i)
add(root, i);
k = 2;
for(i=0; i<n; ++i)
{
k += i;
k %= (n-i);
if(!k) k = n-i;
ans = query(root, k+1);
fout << ans << ' ';
del(root, ans);
}
return 0;
}