Pagini recente » Cod sursa (job #608703) | Cod sursa (job #387357) | Cod sursa (job #1759345) | Cod sursa (job #3169503) | Cod sursa (job #1808112)
#include <bits/stdc++.h>
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;
}
int getKthElement(Nod* rad, int index)
{
assert(0 <= index && index < rad->size);
if (rad->st->size < index)
return getKthElement(rad->dr, index - rad->st->size - 1);
else if (rad->st->size == index)
return rad->val;
else // if (index < rad->st->size)
return getKthElement(rad->st, index);
}
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;
// nodNou->sum = nodNou->val;
pair<Nod*, Nod*> p = split(rad, index);
return join(join(p.first, nodNou), p.second);
}
void deleteAll(Nod* rad)
{
if (rad != emptyNode)
{
deleteAll(rad->st);
deleteAll(rad->dr);
delete rad;
}
}
Nod* eraseAll(Nod* rad, int x1, int x2)
{
assert(0 <= x1 && x1 < x2 && x2 <= rad->size);
pair<Nod*, Nod*> p = split(rad, x2);
pair<Nod*, Nod*> q = split(p.first, x1);
deleteAll(q.second);
return join(q.first, p.second);
}
int main()
{
int n;
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;
//emptyNode->sum = 0;
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));
rad = eraseAll(rad, p, p + 1);
}
printf("\n");
return 0;
}