Submission #1127083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127083		GasmaskChan	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	515 ms	21724 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;
#define ll long long

const int MAX = 1e6 + 5;

int a[1 << 20], f1[1 << 20], f2[1 << 20];
int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
//   freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);
   int n, q;
   cin >> n >> q;
   string s;
   cin >> s;
   for (int i = 0; i < (1 << n); i++) {
      a[i] = s[i] - '0';
      f1[i] = f2[i] = a[i];
   }

   for (int i = 0; i < n; i++) {
      for (int mask = 0; mask < (1 << n); mask++) {
         if (mask >> i & 1) {
            f1[mask] += f1[mask ^ (1 << i)];
         }
         else {
            f2[mask] += f2[mask ^ (1 << i)];
         }
      }
   }

   while (q--) {
      cin >> s;

      int cntA = 0, cntB = 0, cntC = 0;
      int A = 0, B = 0, C = 0;
      for (int i = 0; i < n; i++) {
         if (s[i] == '0') ++cntA, A |= (1 << (n - i - 1));
         else if (s[i] == '1') ++cntB, B |= (1 << (n - i - 1));
         else ++cntC, C |= (1 << (n - i - 1));
      }

      int ans = 0;
      if (cntA < 7) {
         for (int mask = A; mask >= 0; mask--) {
            mask &= A;
            if (__builtin_popcount(mask) & 1) ans -= f2[mask | B];
            else ans += f2[mask | B];
         }
      }
      else if (cntB < 7) {
         for (int mask = B; mask >= 0; mask--) {
            mask &= B;
            if (__builtin_popcount(mask) & 1) ans -= f1[C | (B ^ mask)];
            else ans += f1[C | (B ^ mask)];
         }
      }
      else {
         for (int mask = C; mask >= 0; mask--) {
            mask &= C;
            ans += a[mask | B];
         }
      }

      cout << ans << '\n';
   }
   return 0;
}

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