Cod sursa(job #1808975)

Utilizator mariakKapros Maria mariak Data 18 noiembrie 2016 15:28:49
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
#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;
}