Submission #1100364

#TimeUsernameProblemLanguageResultExecution timeMemory
1100364KietJSnake Escaping (JOI18_snake_escaping)C++17
22 / 100
283 ms21064 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb(x) push_back(x) #define sz(x) (int) x.size() #define all(x) x.begin(), x.end() #define un(x) (x).erase(unique(all(x)), x.end()) typedef long long ll; typedef double db; typedef pair <int, int> ii; typedef pair <ll, ll> pll; typedef vector <ll> V; const int N = 1e7 + 1; const int M = (1 << 20); const int mod = 1e9 + 7; const int inf = 1061109567; const int block = 490; template <class T1, class Gz> void add(T1 &x, Gz y) { x += y; if (x < 0) x += mod; if (x >= mod) x -= mod; } template <class T1, class Gz> bool maximize(T1 &x, Gz y) { if (x < y) { x = y; return true; } return false; } template <class T1, class Gz> bool minimize(T1 &x, Gz y) { if (x > y) { x = y; return true; } return false; } int n, q, a[M]; ll dp[2][M]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for(int i = 0; i < (1 << n); i++) { char x; cin >> x; a[i] = x - '0'; for(int j = 0; j < 2; j++) dp[j][i] = a[i]; } for(int i = 0; i < n; i++) { for(int mask = 0; mask < (1 << n); mask++) { if (mask >> i & 1) { dp[0][mask ^ (1 << i)] += dp[0][mask]; dp[1][mask] += dp[1][mask ^ (1 << i)]; } } } for(int i = 1; i <= q; i++) { string s; cin >> s; reverse(all(s)); vector <int> mask(3, 0); for(int j = 0; j < n; j++) { char x = s[j]; if (x == '0') mask[0] ^= (1 << j); if (x == '1') mask[1] ^= (1 << j); if (x == '?') mask[2] ^= (1 << j); } ll ans = 0; if (__builtin_popcount(mask[2]) <= 6) { ans = a[mask[1]]; for(int mask1 = mask[2]; mask1; mask1 = (mask1 - 1) & mask[2]) { ans += a[mask[1] ^ mask1]; } } else { if (__builtin_popcount(mask[0]) <= 6) { ans = dp[0][mask[1]]; for(int mask1 = mask[0]; mask1; mask1 = (mask1 - 1) & mask[0]) { if (__builtin_popcount(mask1) & 1) { ans -= dp[0][mask[1] ^ mask1]; } else { ans += dp[0][mask[1] ^ mask1]; } } } else { ans = dp[1][mask[1] ^ mask[2]]; for(int mask1 = mask[1]; mask1; mask1 = (mask1 - 1) & mask[1]) { if (__builtin_popcount(mask1) & 1) { ans -= dp[1][mask1 ^ mask[2]]; } else { ans += dp[1][mask1 ^ mask[2]]; } } } } cout << ans << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...