Submission #1117567

#TimeUsernameProblemLanguageResultExecution timeMemory
1117567IcelastSnake Escaping (JOI18_snake_escaping)C++17
100 / 100
1212 ms35688 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; void solve(){ int n, q; cin >> n >> q; string s; cin >> s; int full = (1<<n)-1; vector<int> v(full+1); for(int i = 0; i <= full; i++){ v[i] = s[i]-'0'; } vector<int> f(full+1, 0), g(full+1, 0); for(int mask = 0; mask <= full; mask++){ f[mask] = v[mask]; g[mask] = v[mask]; } for(int i = 0; i < n; i++){ for(int mask = 0; mask <= full; mask++){ if(mask&(1<<i)) f[mask] += f[mask^(1<<i)]; } for(int mask = full; mask >= 0; mask--){ if(!(mask&(1<<i))) g[mask] += g[mask^(1<<i)]; } } for(int i = 1; i <= q; i++){ string s; cin >> s; reverse(s.begin(), s.end()); int A, B, C; A = B = C = 0; int mask0 = 0, mask1 = 0, maskc = 0; vector<int> a, b, c; for(int i = 0; i < n; i++){ if(s[i] == '0'){ A++; a.push_back(i); } if(s[i] == '1'){ B++; b.push_back(i); mask0 += (1<<i); } if(s[i] == '?'){ C++; c.push_back(i); mask1 += (1<<i); }else{ maskc += (1<<i)*(s[i]-'0'); } } int mn = min({A, B, C}); int res = 0; if(mn == A){ for(int mask = 0; mask < (1<<A); mask++){ int nmask = mask0; for(int i = 0; i < A; i++){ if(mask&(1<<i)){ nmask += (1<<a[i]); } } if(__builtin_popcount(mask)&1){ res -= g[nmask]; }else{ res += g[nmask]; } } cout << res << "\n"; continue; } if(mn == B){ for(int mask = 0; mask < (1<<B); mask++){ int nmask = mask1; for(int i = 0; i < B; i++){ if(!(mask&(1<<i))){ nmask += (1<<b[i]); } } if(__builtin_popcount(mask)&1){ res -= f[nmask]; }else{ res += f[nmask]; } } cout << res << "\n"; continue; } if(mn == C){ for(int mask = 0; mask < (1<<C); mask++){ int nmask = maskc; for(int i = 0; i < C; i++){ if(mask&(1<<i)){ nmask += (1<<c[i]); } } res += v[nmask]; } cout << res << "\n"; continue; } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }
#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...