Cod sursa(job #1714757)

Utilizator tudorcomanTudor Coman tudorcoman Data 9 iunie 2016 12:15:27
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;

class Node {
public:
  int val;
  int priority; // max heap
  int size;
  int sum;
  Node *lson;
  Node *rson;
};

Node *emptyNode = new Node{-1, -1, 0, 0, NULL, NULL};

inline void computeSize(Node *root) {
  if(root != emptyNode)
    root->size = 1 + root->lson->size + root->rson->size;
}

void split(Node* root, int k, Node* &first, Node* &second) {
  if(root == emptyNode) {
    first = second = emptyNode;
  } else if(k <= root->lson->size) {
    split(root->lson, k, first, root->lson);
    second = root;
    computeSize(second);
  } else {
    split(root->rson, k - root->lson->size - 1, root->rson, second);
    first = root;
    computeSize(first);
  }
}
void Merge(Node* &root, Node* first, Node* second) {
  if(first == emptyNode) {
    root = second;
    return;
  } else if(second == emptyNode) {
    root = first;
    return;
  }

  if(first->priority < second->priority) {
    Merge(second->lson, first, second->lson);
    root = second;
  } else {
    Merge(first->rson, first->rson, second);
    root = first;
  }

  computeSize(root);
}

void Insert(Node* &root, int value, int priority, int k) {
  if(priority > root->priority) {
    Node *first = new Node{value, priority, 0, 0, NULL, NULL};
    split(root, k - 1, first->lson, first->rson);
    root = first;
    computeSize(root);
    return ;
  }

  if(k <= root->lson->size + 1)
    Insert(root->lson, value, priority, k);
  else
    Insert(root->rson, value, priority, k - root->lson->size - 1);

  computeSize(root);
}

int Erase(Node* &root, int k) {
  int ans = 0;

  if(k <= root->lson->size)
    ans = Erase(root->lson, k);
  else if(k == root->lson->size + 1) {
    Node *l = root;
    int aux = l->val;
    Merge(root, root->lson, root->rson);
    computeSize(root);
    delete l;
    return aux;
  } else
    ans = Erase(root->rson, k - root->lson->size - 1);
  computeSize(root);
  return ans;
}

int main() {
  freopen("order.in", "r", stdin);
  freopen("order.out", "w", stdout);

  srand(time(0));
  Node *root = emptyNode;

  int N = 0;
  scanf("%d", &N);

  for(int i = 1; i <= N; ++ i)
    Insert(root, i, rand(), i);
  int pos = 2;
  for(int i = 1; i <= N; ++ i) {
    pos += i - 1;
    pos = (pos - 1) % (N - i + 1) + 1;
    printf("%d ", Erase(root, pos));
  }
  printf("\n");
  return 0;
}