Submission #1111982

#TimeUsernameProblemLanguageResultExecution timeMemory
1111982_8_8_Snake Escaping (JOI18_snake_escaping)C++17
100 / 100
1888 ms42312 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = (1 << 20) + 12, MOD = (int)1e9 + 7; int l, q, a[N], dp[N], pd[N]; void test() { cin >> l >> q; for(int i = 0; i < (1 << l); i++) { char x; cin >> x; a[i] = (x - '0'); dp[i] = pd[i] = a[i]; } for(int i = 0; i < l; i++) { for(int j = 0; j < (1 << l); j++) { if((j >> i) & 1) { dp[j] += (dp[j - (1 << i)]); } } for(int j = (1 << l) - 1; j >= 0; j--) { if(!((j >> i) & 1)) { pd[j] += pd[j + (1 << i)]; } } } while(q--) { vector<int> d, e, f; int s = 0; for(int i = l - 1; i >= 0; i--) { char x; cin >> x; if(x == '0') { d.push_back(i); } else if(x == '1') { s += (1 << i); e.push_back(i); } else { f.push_back(i); } } int res = 0, m; if((int)f.size() <= 7 ) { m = (int)f.size(); for(int i = 0; i < (1 << m); i++) { int v = s; for(int j = 0; j < m; j++) { if((i >> j) & 1) { v += (1 << f[j]); } } res += a[v]; } } else if((int)e.size() <= 7) { m = (int)e.size(); for(int i:f) { s += (1 << i); } res = 0; for(int i = 0; i < (1 << m); i++) { int v = s; for(int j = 0; j < m; j++) { if((i >> j) & 1) { v -= (1 << e[j]); } } if(__builtin_popcount(i) & 1) { res -= dp[v]; } else { res += dp[v]; } } } else { m = (int)d.size(); for(int i = 0; i < (1 << m); i++) { int v = s; for(int j = 0; j < m; j++) { if((i >> j) & 1) { v += (1 << d[j]); } } if(__builtin_popcount(i) & 1) { res -= pd[v]; } else { res += pd[v]; } } } cout << res << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; // cin >> t; while(t--) test(); }
#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...