Submission #1182097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182097		avighna	Lamps (JOI19_lamps)	C++20	0 / 100	1100 ms	212252 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 tar = x;
        for (int k = i; k <= j; ++k) {
          if (tar & (1 << k)) {
            tar ^= 1 << k;
          }
        }
        ans[tar] = std::min(ans[tar], ans[x] + 1);
        q.push(tar);
        tar = x;
        for (int k = i; k <= j; ++k) {
          if (!(tar & (1 << k))) {
            tar ^= 1 << k;
          }
        }
        ans[tar] = std::min(ans[tar], ans[x] + 1);
        q.push(tar);
        tar = x ^ ((1 << (j + 1)) - (1 << i));
        ans[tar] = std::min(ans[tar], ans[x] + 1);
        q.push(tar);
      }
    }
  }
  std::cout << ans[end] << '\n';
}

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