Submission #1079943

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079943		juicy	Mechanical Doll (IOI18_doll)	C++17	100 / 100	110 ms	10256 KiB

doll

#include "doll.h"

#include <bits/stdc++.h>

using namespace std;

void create_circuit(int m, vector<int> a) {
  a.push_back(0);
  int n = a.size(), s = 1;
  while (s < n) {
    s *= 2;
  }
  vector<int> lt, rt;
  lt.reserve(s);
  rt.reserve(s);
  function<int(int, int)> bld = [&](int l, int r) -> int {
    if (l >= n) {
      return -1;
    }
    if (l == r) {
      return 0;
    }
    int md = (l + r) / 2;
    lt.push_back(0);
    rt.push_back(0);
    int ind = lt.size();
    lt[ind - 1]= bld(l, md);
    rt[ind - 1] = bld(md + 1, r);
    return -ind;
  };
  bld(0, s - 1);
  int node = lt.size();
  vector<int> side(node);
  function<int(int)> crawl = [&](int u) {
    side[u] ^= 1;
    int v = side[u] ? rt[u] : lt[u];
    return !v ? u : crawl(-1 - v);
  };
  for (int x : a) {
    int u = crawl(0);
    (side[u] ? rt[u] : lt[u]) = x;
  }
  answer(vector<int>(m + 1, -1), rt, lt);
}

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