Submission #1245638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245638		kunzaZa183	Mechanical Doll (IOI18_doll)	C++20	100 / 100	111 ms	10212 KiB

doll

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

void create_circuit(int M, vector<int> A) {

  const int mn = 2e5 + 5;
  vector<int> lg2(mn);
  int cur = 1, ct = 0;
  for (int i = 0; i < mn; i++) {
    if (i > cur) {
      cur *= 2;
      ct++;
    }
    lg2[i] = ct;
  }

  A.push_back(0);

  int N = A.size();

  vector<int> c(M + 1), x, y;
  vector<int> stat;

  int num = N;
  int pow2 = (1 << lg2[num]);

  function<int(int, int, int)> build = [&](int curin, int curl, int curr) {
    if (curl >= num) {
      return INT_MIN;
    }
    if (curl == curr) {
      return INT_MAX;
    }
    int a = build(curin * 2 + 1, curl, (curl + curr) / 2),
        b = build(curin * 2 + 2, (curl + curr) / 2 + 1, curr);
    x.push_back(b), y.push_back(a);
    stat.push_back(0);
    return -(int(x.size()));
  };

  int id = build(0, 0, pow2 - 1);

  int in = 0;

  for (int j = 0; j < pow2; j++) {
    vector<int> dfsst;
    dfsst.push_back(id);

    while (!dfsst.empty()) {
      int cur = dfsst.back();
      dfsst.pop_back();

      if (cur >= 0)
        continue;
      int tmp;
      if (stat[-cur - 1] == 0) {
        tmp = x[-cur - 1];
      } else {
        tmp = y[-cur - 1];
      }
      if (stat[-cur - 1] == 0) {
        if (tmp == INT_MAX)
          x[-cur - 1] = A[in++];
        else if (tmp == INT_MIN)
          x[-cur - 1] = id;
        else
          dfsst.push_back(tmp);
      } else {
        if (tmp == INT_MAX)
          y[-cur - 1] = A[in++];
        else if (tmp == INT_MIN)
          y[-cur - 1] = id;
        else
          dfsst.push_back(tmp);
      }
      stat[-cur - 1] = 1 - stat[-cur - 1];
    }
  }

  for (int i = 0; i <= M; i++) {
    c[i] = id;
  }

  answer(c, x, y);
}

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