Submission #445839

#TimeUsernameProblemLanguageResultExecution timeMemory
445839JovanBSnake Escaping (JOI18_snake_escaping)C++17
100 / 100
1774 ms24640 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 20; int str[1<<N]; int sub[1<<N]; int over[1<<N]; int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int n, qrs; cin >> n >> qrs; string td; cin >> td; for(int i=0; i<(1<<n); i++){ str[i] = td[i] - '0'; sub[i] = over[i] = str[i]; } for(int i=0; i<n; i++){ for(int mask=0; mask<(1<<n); mask++){ if(mask & (1 << i)) sub[mask] += sub[mask ^ (1 << i)]; } } for(int i=0; i<n; i++){ for(int mask=0; mask<(1<<n); mask++){ if(!(mask & (1 << i))) over[mask] += over[mask ^ (1 << i)]; } } while(qrs--){ string s; cin >> s; reverse(s.begin(), s.end()); int cp = 0, c1 = 0, c0 = 0; for(auto c : s){ if(c == '?') cp++; else if(c == '0') c0++; else c1++; } int mn = min(min(c0, c1), cp); if(cp == mn){ vector <int> pos; int p = 0; int res = 0; for(int i=0; i<n; i++){ char c = s[i]; if(c == '?') pos.push_back(1 << i); else if(c == '1') p += (1 << i); } if(cp == 0){ cout << str[p] << "\n"; continue; } for(int mask=0; mask<(1<<pos.size()); mask++){ int g = p; int k = mask; while(k){ int x = k & -k; int v = __builtin_ctz(x); g += pos[v]; k -= x; } res += str[g]; } cout << res << "\n"; } else if(c0 == mn){ vector <int> pos; int p = 0; for(int i=0; i<n; i++){ char c = s[i]; if(c == '0') pos.push_back(1 << i); else if(c == '1') p += (1 << i); } if(c0 == 0){ cout << over[p] << "\n"; continue; } int res = 0; for(int mask=0; mask<(1<<pos.size()); mask++){ int g = p, pr = 1; int k = mask; while(k){ int x = k & -k; int v = __builtin_ctz(x); pr = -pr; g += pos[v]; k -= x; } res += pr*over[g]; } cout << res << "\n"; } else{ vector <int> pos; int p = 0; for(int i=0; i<n; i++){ char c = s[i]; if(c != '0') p += (1 << i); if(c == '1') pos.push_back(1 << i); } if(c1 == 0){ cout << sub[p] << "\n"; continue; } int res = 0; for(int mask=0; mask<(1<<pos.size()); mask++){ int g = p, pr = 1; int k = mask; while(k){ int x = k & -k; int v = __builtin_ctz(x); pr = -pr; g -= pos[v]; k -= x; } res += pr*sub[g]; } cout << res << "\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...