Pagini recente » Cod sursa (job #822554) | Cod sursa (job #2348962) | Cod sursa (job #918023) | Cod sursa (job #994999) | Cod sursa (job #2447394)
#include <assert.h>
#include <stdio.h>
#include <algorithm>
using std::pair;
struct Nod
{
Nod* st;
Nod* dr;
int val;
long long key;
int size;
};
Nod* emptyNode;
bool isEmptyNode(Nod* rad) {
return rad == emptyNode;
}
void recompute(Nod* nod) {
nod->size = nod->st->size + 1 + nod->dr->size;
}
pair<Nod*, Nod*> split(Nod* rad, int sizeFirst) {
assert(0 <= sizeFirst && sizeFirst <= rad->size);
pair<Nod*, Nod*> answer;
if (isEmptyNode(rad))
answer.first = answer.second = emptyNode;
else if (rad->st->size < sizeFirst)
{
pair<Nod*, Nod*> p = split(rad->dr, sizeFirst - rad->st->size - 1);
answer.first = rad;
rad->dr = p.first;
answer.second = p.second;
recompute(rad);
}
else // if (sizeFirst <= rad->st->size)
{
pair<Nod*, Nod*> p = split(rad->st, sizeFirst);
answer.second = rad;
rad->st = p.second;
answer.first = p.first;
recompute(rad);
}
return answer;
}
Nod* join(Nod* first, Nod* second) {
if (isEmptyNode(first))
return second;
if (isEmptyNode(second))
return first;
if (second->key > first->key)
{
second->st = join(first, second->st);
recompute(second);
return second;
} else // second->key <= first->key
{
first->dr = join(first->dr, second);
recompute(first);
return first;
}
}
Nod* insert(Nod* rad, int index, int val) {
assert(0 <= index && index <= rad->size);
Nod* nodNou = new Nod();
nodNou->val = val;
nodNou->st = nodNou->dr = emptyNode;
nodNou->key =((long long)rand() << 45
^ (long long)rand() << 30
^ (long long)rand() << 15
^ (long long)rand() << 0)
& 0x7fffffffffffffff;
nodNou->size = 1;
pair<Nod*, Nod*> p = split(rad, index);
return join(join(p.first, nodNou), p.second);
}
int getKthElement(Nod* &rad, int index) {
assert(0 <= index && index < rad->size);
int ret;
if (rad->st->size < index) {
ret = getKthElement(rad->dr, index - rad->st->size - 1);
recompute(rad);
} else if (rad->st->size == index) {
ret = rad->val;
rad = join(rad->st, rad->dr);
} else { // if (index < rad->st->size)
ret = getKthElement(rad->st, index);
recompute(rad);
}
return ret;
}
int main() {
freopen("order.in", "r", stdin);
freopen("order.out", "w", stdout);
emptyNode = new Nod();
emptyNode->val = 0;
emptyNode->key = -1;
emptyNode->st = emptyNode;
emptyNode->dr = emptyNode;
emptyNode->size = 0;
int n;
scanf("%d", &n);
Nod* rad = emptyNode;
for (int i = 1; i <= n; ++ i)
rad = insert(rad, i - 1, i);
int p = 1;
for (int i = 1; i <= n; ++ i)
{
p = (p + i - 1) % (n - i + 1);
printf("%d ", getKthElement(rad, p));
}
printf("\n");
return 0;
}