Pagini recente » Cod sursa (job #2918970) | Cod sursa (job #834502) | Cod sursa (job #2011987) | Cod sursa (job #188419) | Cod sursa (job #1812860)
#include<cstdio>
#include<utility>
#include<cassert>
#include<cstdlib>
using namespace std;
FILE *fin = freopen("order.in", "r", stdin);
FILE *fout = freopen("order.out", "w", stdout);
int N, r;
struct Node
{
Node* left;
Node* right;
int val;
int counter;
long long priority;
};
Node* emptyNode;
pair < Node*, Node* > split(Node* node, int k)
{
//assert(0 <= k && k <= node -> counter);
pair < Node*, Node* > p;
if (node == emptyNode)
{
p.first = emptyNode;
p.second = emptyNode;
}
else
{
if (node -> left -> counter < k)
{
pair < Node*, Node* > q = split(node -> right, k - node -> left -> counter - 1);
p.first = node;
node -> right = q.first;
p.second = q.second;
node -> counter = node -> left -> counter + node -> right -> counter + 1;
}
else
{
pair < Node*, Node* > q = split(node -> left, k);
p.second = node;
node -> left = q.second;
p.first = q.first;
node -> counter = node -> left -> counter + node -> right -> counter + 1;
}
}
return p;
}
Node* join(Node* first, Node* second)
{
if (first == emptyNode)
return second;
if (second == emptyNode)
return first;
if (first -> priority < second -> priority)
{
second -> left = join(second -> left, first);
second -> counter = second -> left -> counter + first -> counter + 1;
return second;
}
else
{
first -> right = join(first -> right, second);
first -> counter = first -> right -> counter + second -> counter + 1;
return first;
}
}
Node* Insert(Node* node, int val, int ind)
{
//assert(0 <= ind && ind <= node -> counter);
Node* newNode = new Node();
newNode -> val = val;
newNode -> counter = 1;
newNode -> left = newNode -> right = emptyNode;
newNode -> priority = ((long long)rand() << 45)
^ ((long long)rand() << 30)
^ ((long long)rand() << 15)
^ ((long long)rand() << 0);
pair < Node*, Node* > p = split(node, ind);
p.first = join(p.first, newNode);
return join(p.first, p.second);
}
int kth_element(Node* &node, int k)
{
int sol = 0;
if (node -> left -> counter < k)
{
sol = kth_element(node -> right, k - node -> left -> counter - 1);
node -> counter = node -> right -> counter + node -> left -> counter + 1;
}
else
if (node -> left -> counter == k)
{
sol = node -> val;
node = join(node -> left, node -> right);
}
else
{
sol = kth_element(node -> left, k);
node -> counter = node -> left -> counter + node -> right -> counter + 1;
}
return sol;
}
int main()
{
scanf("%d", &N);
emptyNode = new Node();
emptyNode -> left = NULL;
emptyNode -> right = NULL;
emptyNode -> val = 0;
emptyNode -> priority = -1;
emptyNode -> counter = 0;
Node* root = emptyNode;
//root = Insert(root, 1, 0);
for (int i = 1; i <= N; i++)
root = Insert(root, i, i - 1);
r = 1;
for (int i = 1; i <= N; i++)
{
r = (r + i - 1) % (N - i + 1);
printf("%d ", kth_element(root, r));
}
}