Submission #1182101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182101		avighna	Lamps (JOI19_lamps)	C++20	6 / 100	735 ms	246480 KiB

lamp

#include <bits/stdc++.h>

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int n;
  std::cin >> n;
  std::string a, b;
  std::cin >> a >> b;

  std::vector<int> vis(1 << n);
  std::vector<int> ans(1 << n, 1e8);
  std::queue<int> q;
  int start = std::stoi(a, nullptr, 2);
  int end = std::stoi(b, nullptr, 2);
  q.push(start);
  ans[start] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    if (vis[x]) {
      continue;
    }
    vis[x] = true;
    if (x == end) {
      break;
    }
    for (int i = 0; i < n; ++i) {
      for (int j = i; j < n; ++j) {
        int mask = (1 << (j + 1)) - (1 << i);
        int tar = x ^ (x & mask);
        ans[tar] = std::min(ans[tar], ans[x] + 1);
        q.push(tar);
        tar = x ^ ((~(x & mask)) & mask);
        ans[tar] = std::min(ans[tar], ans[x] + 1);
        q.push(tar);
        tar = x ^ mask;
        ans[tar] = std::min(ans[tar], ans[x] + 1);
        q.push(tar);
      }
    }
  }
  std::cout << ans[end] << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49