Submission #1196701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196701		aykhn	Mechanical Doll (IOI18_doll)	C++20	53 / 100	69 ms	25672 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>

using namespace std;

void create_circuit(int M, vector<int> A) 
{
  int N = A.size();
  vector<int> nxt[M + 1];
  nxt[0].push_back(A[0]);
  for (int i = 0; i + 1 < N; i++) nxt[A[i]].push_back(A[i + 1]);
  nxt[A.back()].push_back(0);
  vector<int> C(M + 1, 0), X(N * 10), Y(N * 10);
  int cur = 0;
  for (int node = 0; node <= M; node++)
  {
    if (nxt[node].empty()) continue;
    if (nxt[node].size() == 1)
    {
      C[node] = nxt[node][0];
      continue;
    }
    C[node] = -(cur + 1);
    int sz = nxt[node].size();
    int len = 0;
    while ((1 << (len + 1)) < sz) len++;
    for (int i = 1; i < (1 << (len + 1)); i++)
    {
      if (i * 2 >= (1 << (len + 1)))
      {
        X[i + cur - 1] = Y[i + cur - 1] = -(cur + 1);
      }
      else
      {
        X[i + cur - 1] = -(i * 2 + cur);
        Y[i + cur - 1] = -(i * 2 + 1 + cur);
      }
    }
    for (int i = 0; i < nxt[node].size(); i++)
    {
      int nw = 0;
      int left = (1 << (len + 1)) - sz;
      for (int j = 0; j < (len + 1); j++)
      {
        if ((left + i) >> j & 1) nw |= (1 << (len - j));
      }
      int par = (nw / 2) + (1 << len);
      if (nw & 1) Y[par + cur - 1] = nxt[node][i];
      else X[par + cur - 1] = nxt[node][i];
    }
    cur += (1 << (len + 1)) - 1;
  }
  while (X.size() > cur) X.pop_back();
  while (Y.size() > cur) Y.pop_back();
  // for (int &i : C) cout << i << ' ';
  // cout << '\n';
  // for (int &i : X) cout << i << ' ';
  // cout << '\n';
  // for (int &i : Y) cout << i << ' ';
  // cout << '\n';
  // cout << endl;
  answer(C, X, Y);
}

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