Submission #1035232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035232		juicy	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	580 ms	42232 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

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

  int L, Q; cin >> L >> Q;
  vector dp(2, vector<int>(1 << L));
  vector<int> A(1 << L);
  for (int i = 0; i < (1 << L); ++i) {
    char c; cin >> c;
    A[i] = c - '0';
    for (int j = 0; j < 2; ++j) {
      dp[j][i] += A[i];
    }
  }
  for (int i = 0; i < L; ++i) {
    for (int mask = 0; mask < (1 << L); ++mask) {
      int c = mask >> i & 1;
      dp[c][mask] += dp[c][mask ^ (1 << i)];
    }
  }
  auto conv = [&](char c) {
    return c == '?' ? 2 : c - '0';
  };
  while (Q--) {
    array<int, 3> m{}, fre{};
    for (int i = L - 1; i > -1; --i) {
      char c; cin >> c;
      int x = conv(c);
      ++fre[x];
      m[x] += 1 << i;
    }
    long long res = 0;
    if (fre[0] <= fre[1] && fre[0] <= fre[2]) {
      for (int sm = m[0]; sm; sm = (sm - 1) & m[0]) {
        int cnt = __builtin_popcount(sm);
        res += (cnt & 1 ? -1 : 1) * dp[0][sm | m[1]];
      }
      res += dp[0][m[1]];
    } else if (fre[1] <= fre[0] && fre[0] <= fre[2]) {
      for (int sm = m[1]; sm; sm = (sm - 1) & m[1]) {
        int M = m[1] ^ sm;
        int cnt = __builtin_popcount(M);
        M |= m[2];
        res += (cnt % 2 == fre[1] % 2 ? 1 : -1) * dp[1][M];
      }
      res += dp[1][m[1] | m[2]];
    } else {
      for (int sm = m[2]; sm; sm = (sm - 1) & m[2]) {
        res += A[sm | m[1]];
      }
      res += A[m[1]];
    }
    cout << res << "\n";
  }
  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25