Pagini recente » Cod sursa (job #1023745) | Cod sursa (job #935768) | Cod sursa (job #2425846) | Cod sursa (job #1005870) | Cod sursa (job #1808975)
#include <assert.h>
#include <stdio.h>
#include <algorithm>
FILE *fin = freopen("order.in", "r", stdin);
FILE *fout = freopen("order.out", "w", stdout);
using std::pair;
struct Node
{
Node* left;
Node* right;
int value;
long long priority;
int count;
};
Node* emptyNode;
void recompute(Node* node) {
node->count = node->left->count + node->right->count + 1;
}
pair<Node*, Node*> split(Node* root, int kth) {
assert(0 <= kth && kth <= root->count);
pair<Node*, Node*> ans;
if (root == emptyNode)
ans.first = ans.second = emptyNode;
else if (root->left->count < kth)
{
pair<Node*, Node*> p = split(root->right, kth - root->left->count - 1);
ans.first = root;
root->right = p.first;
ans.second = p.second;
recompute(root);
}
else
{
pair<Node*, Node*> p = split(root->left, kth);
ans.second = root;
root->left = p.second;
ans.first = p.first;
recompute(root);
}
return ans;
}
Node* join(Node* first, Node* second) {
if (first == emptyNode)
return second;
if (second == emptyNode)
return first;
if (second->priority > first->priority)
{
second->left = join(first, second->left);
recompute(second);
return second;
} else
{
first->right = join(first->right, second);
recompute(first);
return first;
}
}
Node* insert(Node* root, int idx, int value) {
assert(0 <= idx && idx <= root->count);
Node* newNode = new Node();
newNode->value = value;
newNode->left = newNode->right = emptyNode;
newNode->priority =((long long)rand() << 45
^ (long long)rand() << 30
^ (long long)rand() << 15
^ (long long)rand() << 0)
& 0x7fffffffffffffff;
newNode->count = 1;
pair<Node*, Node*> p = split(root, idx);
return join(join(p.first, newNode), p.second);
}
int Kth_Element(Node* &root, int idx) {
assert(0 <= idx && idx < root->count);
int res;
if (root->left->count < idx) {
res = Kth_Element(root->right, idx - root->left->count - 1);
recompute(root);
} else if (root->left->count == idx) {
res = root->value;
root = join(root->left, root->right);
} else {
res = Kth_Element(root->left, idx);
recompute(root);
}
return res;
}
int main() {
emptyNode = new Node();
emptyNode->value = 0;
emptyNode->priority = -1;
emptyNode->left = emptyNode;
emptyNode->right = emptyNode;
emptyNode->count = 0;
int n;
scanf("%d", &n);
Node* root = emptyNode;
for (int i = 1; i <= n; ++ i)
root = insert(root, i - 1, i);
int p = 1;
for (int i = 1; i <= n; ++ i)
{
p = (p + i - 1) % (n - i + 1);
printf("%d ", Kth_Element(root, p));
}
printf("\n");
return 0;
}