Submission #958618

#	Time	Username	Problem	Language	Result	Execution time	Memory
958618		AkibAzmain	Mechanical Doll (IOI18_doll)	C++17	100 / 100	93 ms	10324 KiB

doll

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

void create_circuit(int m, std::vector<int> a) {
  a.push_back (0);
  int n = a.size (), vt = 1;
  while (vt < n) vt <<= 1;
  int ivt = 1e9, ust;
  vector < int > c (m + 1), x, y;
  auto f = [&] (auto &self, int l, int r) -> int
  {
    if (r <= 0) return ivt;
    if (l + 1 == r) return ust;
    int m = (l + r) / 2;
    int a = self (self, l, m), b = self (self, m, r);
    x.push_back (a), y.push_back (b);
    return -x.size ();
  };
  int fs = f (f, n - vt, n);
  for (auto &x : c) x = fs;
  for (auto &xx : x) if (xx == ivt) xx = fs;
  for (auto &xx : y) if (xx == ivt) xx = fs;
  int ai = 0;
  vector < bool > st (x.size ());
  for (int i = 0; i < n; ++i)
    for (int *i = &fs; ; st[-(*i + 1)] = !st[-(*i + 1)],
           i = st[-(*i + 1)] ? &x[-(*i + 1)] : &y[-(*i + 1)])
      if (*i == ust)
        {
           *i = a[ai++];
           break;
        }
  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