Submission #102844

#	Time	Username	Problem	Language	Result	Execution time	Memory
102844		wxh010910	Mechanical Doll (IOI18_doll)	C++17	100 / 100	114 ms	10788 KiB

doll

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

using namespace std;

const int inf = 0x3f3f3f3f;

void create_circuit(int m, vector<int> a) {
  int n = a.size(), base = 1;
  a.push_back(0);
  while (base < n) {
    base <<= 1;
  }
  vector<int> rev(base);
  for (int i = 0; i < base; ++i) {
    rev[i] = rev[i >> 1] >> 1 | (i & 1 ? base >> 1 : 0);
  }
  vector<int> real(base, -1);
  for (int i = base - n; i < base; ++i) {
    real[rev[i]] = i;
  }
  vector<int> id(base);
  for (int i = 0, total = 0; i < base; ++i) {
    if (~real[i]) {
      id[real[i]] = ++total;
    }
  }
  
  vector<int> x, y;
  
  function<int(int, int)> build = [&](int l, int r) {
    if (l == r - 1) {
      if (l >= base - n) {
        return a[id[l]];
      } else {
        return inf;
      }
    } else {
      int m = l + r >> 1;
      int left = build(l, m);
      int right = build(m, r);
      if (left == inf && right == inf) {
        return inf;
      } else {
        x.push_back(left);
        y.push_back(right);
        return -(int)x.size();
      }
    }
  };

  int root = build(0, base);
  vector<int> c(m + 1, root);
  c[0] = a[0];
  for (int i = 0; i < -root; ++i) {
    if (x[i] == inf) {
      x[i] = root;
    }
    if (y[i] == inf) {
      y[i] = root;
    }
  }
  answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In lambda function:
doll.cpp:39:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |       int m = l + r >> 1;
      |               ~~^~~

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