Pagini recente » Cod sursa (job #60218) | Cod sursa (job #2592773) | Cod sursa (job #1910692) | Cod sursa (job #1324553) | Cod sursa (job #2538878)
#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) {
val = v;
priority = p;
left = 0; right = 0;
subarb = 0;
}
};
Treap *T = new Treap;
int getRandom() {
return 1LL * rand() % 10000 * 10000 + rand() % 10000;
}
void rotToRight(Treap *nod) {
Treap *oldNodLR = nod->left->right;
nod->left->right = nod;
nod = nod->left;
nod->right->left = oldNodLR;
}
void rotToLeft(Treap *nod) {
Treap *oldNodRL = nod->right->left;
nod->right->left = nod;
nod = nod->right;
nod->left->right = oldNodRL;
}
void balans(Treap *nod) {
// un fiu posibil sa nu fie bine ca heap
if (nod->left && nod->left->priority > nod->priority) {
rotToRight(nod);
}
else if (nod->right && nod->right->priority > nod->priority) {
rotToLeft(nod);
}
}
void baga(Treap *nod, int val) {
if (nod == 0) {
// aici
nod = Treap(val, getRandom());
return;
}
if (val <= R->val) {
// stanga
baga(nod->left, val);
}
else {
// dreapta
baga(nod->right, val);
}
balans(nod);
}
int kthElement(Treap *nod, int k) {
}
int main()
{
fi >> n;
for (int i = 1; i <= n; i++) {
baga(R, i);
}
int curr = 1, total = n;
for (int i = 1; i <= n; i++) {
fo << kthElement(R, curr) << " ";
total--;
curr = (curr + i - 1) % total;
if (curr == 0)
curr = total;
}
return 0;
}