Cod sursa(job #1939628)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 25 martie 2017 21:12:47
Problema Order Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>

class OutParser {
 private:
  FILE *fout;
  char *buff;
  int sp;

  void write_ch(char ch) {
    if (sp == 50000) {
      fwrite(buff, 1, 50000, fout);
      sp = 0;
      buff[sp++] = ch;
    } else {
      buff[sp++] = ch;
    }
  }


 public:
  OutParser(const char* name) {
    fout = fopen(name, "w");
    buff = new char[50000]();
    sp = 0;
  }
  ~OutParser() {
    fwrite(buff, 1, sp, fout);
    fclose(fout);
  }

  OutParser& operator << (int vu32) {
    if (vu32 <= 9) {
      write_ch(vu32 + '0');
    } else {
      (*this) << (vu32 / 10);
      write_ch(vu32 % 10 + '0');
    }
    return *this;
  }

  OutParser& operator << (long long vu64) {
    if (vu64 <= 9) {
      write_ch(vu64 + '0');
    } else {
      (*this) << (vu64 / 10);
      write_ch(vu64 % 10 + '0');
    }
    return *this;
  }

  OutParser& operator << (char ch) {
    write_ch(ch);
    return *this;
  }
  OutParser& operator << (const char *ch) {
    while (*ch) {
      write_ch(*ch);
      ++ch;
    }
    return *this;
  }
};

OutParser fout("order.out");

struct Node {
  int val;
  int size;
  int priority;
  Node* left;
  Node* right;
  bool reversed;
};

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

void unreverse(Node* root) {
  if (root != emptyNode && root->reversed) {
    std::swap(root->left, root->right);
    root->left->reversed = !root->left->reversed;
    root->right->reversed = !root->right->reversed;
    root->reversed = false;
  }
}

void recompute(Node* root) {
  root->size = root->left->size + 1 + root->right->size;
}

std::pair<Node*, Node*> split(Node* root, int k) {
  unreverse(root);
  std::pair<Node*, Node*> answer;
  if (root == emptyNode) {
    answer.first = emptyNode;
    answer.second = emptyNode;
  } else if (k <= root->left->size) {
    answer.second = root;
    auto p = split(root->left, k);
    answer.first = p.first;
    answer.second->left = p.second;
    recompute(answer.second);
  } else {
    answer.first = root;
    auto p = split(root->right, k - root->left->size - 1);
    answer.first->right = p.first;
    recompute(answer.first);
    answer.second = p.second;
  }
  return answer;
}

Node* join(Node* root1, Node* root2) {
  unreverse(root1);
  unreverse(root2);
  if (root1 == emptyNode) {
    return root2;
  } else if (root2 == emptyNode) {
    return root1;
  } else if (root1->priority > root2->priority) {
    root1->right = join(root1->right, root2);
    recompute(root1);
    return root1;
  } else {
    root2->left = join(root1, root2->left);
    recompute(root2);
    return root2;
  }
}

Node* insert(Node* root, int k, Node* val) {
  auto p = split(root, k - 1);
  return join(join(p.first, val), p.second);
}

Node* insert(Node* root, int k, int val) {
  return insert(root, k, new Node{val, 1, rand(), emptyNode, emptyNode, false});
}

Node* erase(Node* root, int k) {
  auto p1 = split(root, k - 1);
  auto p2 = split(p1.second, 1);
  fout << p2.first->val << ' ';
  delete p2.first;
  return join(p1.first, p2.second);
}

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

  srand(time(0));

  int N;

  scanf("%d", &N);

  Node* root = emptyNode;

  for (int i = 1; i <= N; ++i)
    root = insert(root, i, i);

  int start = 1, copie = N;

  for (; N >= 1; --N) {
    start = (start + (copie - N + 1)) % N;
    if (start == 0)
      start = N;
    root = erase(root, start);
    start--;
    if (start == 0)
      start = N - 1;
  }

  return 0;
}