Pagini recente » Cod sursa (job #1810489) | Cod sursa (job #2748234) | Cod sursa (job #1919565) | Cod sursa (job #1412201) | Cod sursa (job #2543354)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("order.in");
ofstream fo("order.out");
struct Treap {
Treap *left, *right;
int val, priority;
int subarb;
Treap(int v, int p, int subarb, Treap *l, Treap *r) {
this->val = v;
this->priority = p;
this->left = l; this->right = l;
this->subarb = subarb;
}
} *T, *nil;
int n;
int getRandom() {
return 1LL * rand() % 10000 * 10000 + rand() % 10000;
}
void updSubarbore(Treap *nod) {
if (nod == nil)
return;
nod->subarb = 1 + nod->left->subarb + nod->right->subarb;
}
void rotToRight(Treap *&nod) {
Treap *t = nod->left;
nod->left = t->right, t->right = nod;
nod = t;
updSubarbore(nod->right);
updSubarbore(nod->left);
updSubarbore(nod);
}
void rotToLeft(Treap *&nod) {
Treap *t = nod->right;
nod->right = t->left; t->left = nod;
nod = t;
updSubarbore(nod->right);
updSubarbore(nod->left);
updSubarbore(nod);
}
void balans(Treap *&nod) {
// un fiu posibil sa nu fie bine ca heap
if (nod->left->priority > nod->priority) {
rotToRight(nod);
}
else if (nod->right->priority > nod->priority) {
rotToLeft(nod);
}
}
void baga(Treap *&nod, int val) {
if (nod == nil) {
// aici
nod = new Treap(val, getRandom(), 1, nil, nil);
return;
}
if (val <= nod->val) {
// stanga
baga(nod->left, val);
updSubarbore(nod);
}
else {
// dreapta
baga(nod->right, val);
updSubarbore(nod);
}
balans(nod);
}
bool cauta(Treap *nod, int x) {
if (nod == nil)
return 0;
if (nod->val == x)
return 1;
if (x <= nod->val)
return cauta(nod->left, x);
else
return cauta(nod->right, x);
}
void scoate(Treap *&nod, int val) {
if (nod == nil)
return;
if (val < nod->val) {
scoate(nod->left, val);
updSubarbore(nod);
}
else if (val > nod->val) {
scoate(nod->right, val);
updSubarbore(nod);
}
else {
// sunt aici si vreau sa cobor. il aduc pe fiul cu prioritate mai mare
if (nod->left == nil && nod->right == nil) {
delete nod;
nod = nil;
}
else {
if (nod->left->priority > nod->right->priority)
rotToRight(nod);
else
rotToLeft(nod);
scoate(nod, val);
}
}
}
int kthElement(Treap *nod, int k) {
if (nod == nil)
return -1;
// st: 1...nod->left->subarb
if (k <= nod->left->subarb)
return kthElement(nod->left, k);
else if (k == nod->left->subarb + 1)
return nod->val;
else
return kthElement(nod->right, k - (nod->left->subarb + 1));
}
int main()
{
srand(time(NULL));
T = nil = new Treap(0, 0, 0, NULL, NULL);
fi >> n;
for (int i = 1; i <= n; i++) {
baga(T, i);
}
int curr = 2, total = n;
for (int i = 2; i <= n; i++) {
int x = kthElement(T, curr);
fo << x << " ";
scoate(T, x);
total--;
curr = (curr + i - 1) % total;
if (curr == 0)
curr = total;
}
fo << kthElement(T, curr);
return 0;
}