Submission #1245616

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245616		kunzaZa183	Mechanical Doll (IOI18_doll)	C++20	26 / 100	1093 ms	33636 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;
  map<int, array<int, 2>> mivi;
  map<int, 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);
      mivi[-(int(x.size()))] = {x.back(), y.back()};
      return -(int(x.size()));
    };

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

    int in = 0;
    function<void(int)> dfs = [&](int cur) {
      if (cur >= 0)
        return;
      int tmp = mivi[cur][stat[cur]];
      if (stat[cur] == 0) {
        if (tmp == INT_MAX)
          x[-cur - 1] = adj[i][in++];
        else if (tmp == INT_MIN)
          x[-cur - 1] = c[i];
        else
          dfs(tmp);
      } else {
        if (tmp == INT_MAX)
          y[-cur - 1] = adj[i][in++];
        else if (tmp == INT_MIN)
          y[-cur - 1] = c[i];
        else
          dfs(tmp);
      }
      stat[cur] = 1 - stat[cur];
    };

    for (int j = 0; j < pow2; j++)
      dfs(c[i]);
  }

  answer(c, x, y);
}

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