Submission #775527

#TimeUsernameProblemLanguageResultExecution timeMemory
7755271binSnake Escaping (JOI18_snake_escaping)C++14
100 / 100
1410 ms43348 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; int n, q, a[1 << 20], S[1 << 20], T[1 << 20], cnt[2], ans, p; string s; void f(int i, int op, int st){ if(i == n){ if(!op) ans += a[st]; else if(op == 1){ if(p & 1) ans -= S[st]; else ans += S[st]; } else{ if(p & 1) ans -= T[st]; else ans += T[st]; //cout << i << ' ' << st << ' ' << T[st] << ' ' << ans << '\n'; } return; } if(!op){ if(s[i] == '?') { f(i + 1, op, st); f(i + 1, op, st | 1 << i); } else { if(s[i] == '1') st |= 1 << i; f(i + 1, op, st); } } else if(op == 1){ if(s[i] == '1'){ f(i + 1, op, st | 1 << i); p++; f(i + 1, op, st); p--; } else{ if(s[i] == '?') st |= 1 << i; f(i + 1, op, st); } } else{ if(s[i] == '0'){ f(i + 1, op, st); p++; f(i + 1, op, st | 1 << i); p--; } else{ if(s[i] == '1') st |= 1 << i; f(i + 1, op, st); } } return; } int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q >> s; for(int i = 0; i < 1 << n; i++) { a[i] = s[i] - '0'; S[i] = T[i] = a[i]; } for(int i = 0; i < n; i++) for(int mask = 0; mask < 1 << n; mask++) { if(mask & (1 << i)) S[mask] += S[mask ^ (1 << i)]; if(!(mask & (1 << i))) T[mask] += T[mask ^ (1 << i)]; } while(q--){ cin >> s; reverse(all(s)); cnt[0] = cnt[1] = 0; for(int i = 0; i < n; i++){ if(s[i] == '?') cnt[0]++; else if(s[i] == '1') cnt[1]++; } ans = 0; if(cnt[0] <= n / 3) f(0, 0, 0); else if(cnt[1] <= n / 3) f(0, 1, 0); else f(0, 2, 0); 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...