Submission #1194621

#TimeUsernameProblemLanguageResultExecution timeMemory
1194621LucaIlieSnake Escaping (JOI18_snake_escaping)C++20
0 / 100
1 ms320 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 20; int cost[1 << MAX_N], sumDown[1 << MAX_N], sumUp[1 << MAX_N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; string c; cin >> n >> q; cin >> c; for (int mask = 0; mask < (1 << n); mask++) cost[mask] = sumDown[mask] = sumUp[mask] = c[mask] - '0'; for (int i = 0; i < n; i++) { for (int mask = 0; mask < (1 << n); mask++) { if ((mask >> i) & 1) sumDown[mask] += sumDown[mask ^ (1 << i)]; } } for (int i = 0; i < n; i++) { for (int mask = (1 << n) - 1; mask >= 0; mask--) { if (!((mask >> i) & 1)) sumUp[mask] += sumUp[mask ^ (1 << i)]; } } for (int mask = (1 << n) - 1; mask >= 0; mask--) printf("%d %d\n", mask, sumUp[mask]); while (q--) { string s; cin >> s; reverse(s.begin(), s.end()); vector<int> pq, p0, p1; for (int i = 0; i < n; i++) { if (s[i] == '?') pq.push_back(i); else if (s[i] == '0') p0.push_back(i); else p1.push_back(i); } int ans = 0; if ((int)p0.size() <= 6) { int mask = 0; for (int i = 0; i < n; i++) mask += ((s[i] == '1') << i); for (int fixed = 0; fixed < (1 << p0.size()); fixed++) { int newMask = mask, cnt = 0; for (int i = 0; i < (int)p0.size(); i++) { if ((fixed >> i) & 1) { cnt++; newMask += (1 << p0[i]); } } if (cnt % 2 == 0) ans += sumUp[newMask]; else ans -= sumUp[newMask]; } } else if ((int)p1.size() <= 6) { int mask = 0; for (int i = 0; i < n; i++) mask += ((s[i] != '0') << i); for (int fixed = 0; fixed < (1 << p1.size()); fixed++) { int newMask = mask, cnt = 0; for (int i = 0; i < (int)p1.size(); i++) { if ((fixed >> i) & 1) { cnt++; newMask -= (1 << p1[i]); } } if (cnt % 2 == 0) ans += sumDown[newMask]; else ans -= sumDown[newMask]; } } else { int mask = 0; for (int i = 0; i < n; i++) mask += ((s[i] == '1') << i); for (int fixed = 0; fixed < (1 << pq.size()); fixed++) { int newMask = mask; for (int i = 0; i < (int)pq.size(); i++) { if ((fixed >> i) & 1) newMask += (1 << pq[i]); } ans += cost[newMask]; } } 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...