Submission #252188

#TimeUsernameProblemLanguageResultExecution timeMemory
252188NightlightSnake Escaping (JOI18_snake_escaping)C++14
0 / 100
1 ms384 KiB
#include <bits/stdc++.h> using namespace std; int L, Q; char ch; int A[1 << 20]; int dp0[1 << 20];//1 jadi 1, semua 0 jadi ? int dp1[1 << 20];//0 jadi 0, semua 1 jadi ? int main() { ios_base::sync_with_stdio(0); cin >> L >> Q; for(int i = 0; i < (1 << L); i++) { cin >> ch; A[i] = ch - '0'; dp0[i] = dp1[i] = A[i]; } for(int i = 0; i < L; i++) { for(int mask = 0; mask < (1 << L); mask++) { if(mask & (1 << i)) { dp1[mask] += dp1[mask ^ (1 << i)]; }else dp0[mask] += dp0[mask ^ (1 << i)]; } } // cout << "-> " << dp0[0] << "\n"; // cout << "-> " << dp0[(1 << L) - 1] << "\n"; int mask1, mask0, maskq; int cnt1, cnt0, cntq; int ans, tmp, bit; while(Q--) { ans = mask1 = mask0 = maskq = cnt1 = cnt0 = cntq = 0; for(int i = L - 1; i >= 0; i--) { cin >> ch; if(ch == '0') mask0 |= (1 << i), cnt0++; if(ch == '1') mask1 |= (1 << i), cnt1++; if(ch == '?') maskq |= (1 << i), cntq++; } if(cntq <= cnt0 && cntq <= cnt1) { tmp = maskq; while(tmp) { // cout << Q << ": " << A[mask1 | tmp] << " " << A[mask1] << "\n"; ans += A[mask1 | tmp]; tmp = maskq & (tmp - 1); } printf("%d\n", ans + A[mask1]); }else if(cnt0 <= cnt1){ tmp = mask0; while(tmp) { ans += dp0[mask1 | tmp] * -(__builtin_popcount(tmp) & 1); tmp = mask0 & (tmp - 1); } printf("%d\n", ans + dp0[mask1]); }else { tmp = mask1; while(tmp) { bit = (((1 << L) - 1) ^ mask1); ans += dp1[maskq | bit] * -(__builtin_popcount(bit) & 1); tmp = mask1 & (tmp - 1); } printf("%d\n", ans + dp1[maskq + mask1]); } }; }
#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...