Submission #1245622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245622		kunzaZa183	Mechanical Doll (IOI18_doll)	C++20	85.55 / 100	115 ms	12976 KiB

doll

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

void answer(vector<int> a, vector<int> b, vector<int> c);

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;
  }

  int N = A.size();

  vector<vector<int>> adj(M + 1);

  adj[0].push_back(A[0]);
  for (int i = 0; i + 1 < A.size(); i++) {
    adj[A[i]].push_back(A[i + 1]);
  }
  adj[A.back()].push_back(0);

  vector<int> c(M + 1), x, y;
  vector<int> stat;
  for (int i = 0; i <= M; i++) {

    if (adj[i].empty()) {
      c[i] = 0;
      continue;
    }

    if (adj[i].size() == 1) {
      c[i] = adj[i][0];
      continue;
    }

    int num = adj[i].size();
    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()));
    };

    c[i] = build(0, 0, pow2 - 1);

    int in = 0;

    for (int j = 0; j < pow2; j++) {
      vector<int> dfsst;
      dfsst.push_back(c[i]);

      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] = adj[i][in++];
          else if (tmp == INT_MIN)
            x[-cur - 1] = c[i];
          else
            dfsst.push_back(tmp);
        } else {
          if (tmp == INT_MAX)
            y[-cur - 1] = adj[i][in++];
          else if (tmp == INT_MIN)
            y[-cur - 1] = c[i];
          else
            dfsst.push_back(tmp);
        }
        stat[-cur - 1] = 1 - stat[-cur - 1];
      }
    }
  }

  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: 41.553 / 56