Submission #630458

#	Time	Username	Problem	Language	Result	Execution time	Memory
630458		abeker	Mechanical Doll (IOI18_doll)	C++17	37 / 100	121 ms	11796 KiB

doll

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

void create_circuit(int M, vector <int> a) {
  int N = a.size(), offset = 1;
  while (offset <= N)
    offset *= 2;
  int curr = 1, cnt = 0;
  vector <int> state(offset);
  vector <int> pos(offset);
  while (cnt < offset)
    if (curr < offset) {
      int nxt = 2 * curr + state[curr];
      state[curr] ^= 1;
      curr = nxt;
    }
    else {
      pos[curr - offset] = cnt++;
      curr = 1;
    }
  vector <int> x(offset - 1), y(offset - 1);
  for (int i = 1; i < offset; i++) {
    auto get_next = [&](int node) {
      if (node < offset)
        return -node;
      node = pos[node - offset];
      if (node < N)
        return a[node];
      return node == offset - 1 ? 0 : -1;
    };
    x[i - 1] = get_next(2 * i);
    y[i - 1] = get_next(2 * i + 1);
  }
  answer(vector <int> (M + 1, -1), x, y);
}

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