Submission #604559

#	Time	Username	Problem	Language	Result	Execution time	Memory
604559		piOOE	Mechanical Doll (IOI18_doll)	C++17	53 / 100	201 ms	14852 KiB

doll

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

using namespace std;

void create_circuit(int m, vector<int> a) {
  int n = (int) a.size();
  vector<int> c(m + 1, 0), x, y;
  c[0] = a[0];
  a.push_back(0);
  vector<vector<int>> g(m + 1);
  for (int i = 0; i < n; ++i) {
    g[a[i]].push_back(a[i + 1]);
  }
  vector<int> left;
  for (int i = 1; i <= m; ++i) {
    if (!g[i].empty()) {
      function<int(vector<int>)> solve = [&](vector<int> z) -> int {
        if (z.size() == 1) {
          return z[0];
        }
        int last = -((int) x.size() + 1);
        x.push_back(0), y.push_back(0);
        vector<int> L, R;
        for (int i = 0; i < (int) z.size(); ++i) {
          if (i & 1 ^ 1) {
            L.push_back(z[i]);
          } else {
            R.push_back(z[i]);
          }
        }
        if (L.size() > R.size()) {
          R.push_back(L.back());
          L.back() = last;
        }
        int ll = solve(L), rr = solve(R);
        x[-last - 1] = ll, y[-last - 1] = rr;
        return last;
      };
      c[i] = solve(g[i]);
    }
  }
  answer(c, x, y);
}

Compilation message (stderr)

doll.cpp: In lambda function:
doll.cpp:26:17: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   26 |           if (i & 1 ^ 1) {
      |               ~~^~~

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