Submission #827782

#	Time	Username	Problem	Language	Result	Execution time	Memory
827782		WLZ	Mechanical Doll (IOI18_doll)	C++17	84 / 100	116 ms	15868 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

struct node {
  int idx, state;
  node *left, *right;
};

int n, m, cur_idx = 0, max_depth = 0, next_power = 1;
vector<int> a, c, x, y;
set<int> removed_bits;

node *build(int l, int r, int pw, int depth = 0) {
  max_depth = max(max_depth, depth);
  if (pw == 1) return nullptr;
  if (((next_power - n) & pw) && !removed_bits.count(pw)) {
    removed_bits.insert(pw);
    return nullptr;
  }
  x.push_back(-1); y.push_back(-1);
  node *ans = new node{cur_idx++, 0, nullptr, nullptr};
  ans->left = build(l, r - pw / 2, pw / 2, depth + 1);
  ans->right = build(r - pw / 2 + 1, r, pw / 2, depth + 1);
  if (ans->left != nullptr) x[ans->idx] = -(ans->left->idx + 1);
  if (ans->right != nullptr) y[ans->idx] = -(ans->right->idx + 1);
  return ans;
}

void create_circuit(int M, std::vector<int> A) {
  n = (int) A.size(), m = M, a = A;
  c.resize(m + 1); c[0] = a[0];
  for (int i = 1; i <= M; i++) c[i] = -1;
  a.erase(a.begin()); a.push_back(0);
  while (next_power < n) next_power *= 2;
  node *root = build(0, n - 1, next_power); node *cur = root;
  int ptr = 0;
  bool first = n % 2;
  while (ptr < n) {
    int depth = 1;
    while ((cur->state == 0 && cur->left != nullptr) || (cur->state == 1 && cur->right != nullptr)) {
      depth++;
      cur->state = !cur->state;
      if (cur->state == 1) cur = cur->left;
      else cur = cur->right;
    }
    if (depth == max_depth && ptr < n) {
      if (!first) {
        if (cur->state == 0) x[cur->idx] = a[ptr++];
        else y[cur->idx] = a[ptr++];
      }
      first = false;
    }
    cur->state = !cur->state;
    cur = root;
  }
  answer(c, x, y);
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 18 / 18
• Subtask 6: 56 / 56