Submission #1146753

#TimeUsernameProblemLanguageResultExecution timeMemory
1146753mansurSnake Escaping (JOI18_snake_escaping)C++17
0 / 100
1 ms324 KiB
#include<bits/stdc++.h> using namespace std; //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3") #define pb push_back #define ll long long //#define sort(all(v)) sort(v.begin(),v.end()) int mod = 998244353; const int N = 1e5 + 10; const int inf = 1e9; signed main() { //freopen("mootube.in", "r", stdin); //freopen("mootube.out", "w", stdout); int l,q; cin >> l >> q; string s; cin >> s; vector <ll> dp((1 << l)),dp1((1 << l)); for(int i = 0; i < (1 << l); i++) { dp[i] = dp1[i] = s[i] - '0'; } for(int i = 0; i < l; i++) { for(int mask = (1 << l) - 1; mask >= 0; mask--) { if(!(mask >> i & 1)) { dp1[mask] += dp1[(mask ^ (1 << i))]; } } } for(int i = 0; i < l; i++) { for(int mask = 0; mask < (1 << l) ; mask++) { if((mask >> i & 1)) { dp[mask] += dp[(mask ^ (1 << i))]; } } } while(q--) { string t; cin >> t; int cnt = 0,cnt1 = 0; for(int i = 0; i < l; i++) { if(t[i] == '?') cnt++; else if(t[i] == '1') cnt1++; } if(cnt <= 6) { int sum = 0,p = 0; ll ans = 0; vector <int> v; for(int i = t.size() - 1; i >= 0; i--) { if(t[i] == '1') { sum += (1 << p); } else if(t[i] == '?') { v.pb(p); } p++; } for(int mask = 0; mask < (1 << cnt); mask++) { int sum1 = 0; for(int j = 0; j < cnt; j++) { if((mask >> j & 1) == 1) { sum1 += (1 << v[j]); } } ans += s[sum + sum1] - '0'; } cout << ans << '\n'; } else if(cnt1 > 6) { int p = 0,sum = 0; ll ans = 0; for(int i = t.size() - 1; i >= 0; i--) { if(t[i] == '1') sum += (1 << p); p++; } ans = dp1[sum]; vector <int> v; p = 0; for(int i = t.size() - 1; i >= 0; i--) { if(t[i] == '0') v.pb(p); p++; } for(int mask2 = 1; mask2 < (1 << v.size()); mask2++) { int sum1 = sum; for(int j = 0; j < v.size(); j++) { if((mask2 >> j & 1) == 1)sum1 += (1 << v[j]); } if(__builtin_popcount(mask2) & 1) { ans -= dp1[sum1]; } else ans += dp1[sum1]; } cout << ans << '\n'; } else { int p = 0,sum = 0; ll ans = 0; for(int i = t.size() - 1; i >= 0; i--) { if(t[i] == '1') sum += (1 << p); p++; } ans = dp[sum]; vector <int> v; p = 0; for(int i = t.size() - 1; i >= 0; i--) { if(t[i] == '1') v.pb(p); p++; } for(int mask2 = 1; mask2 < (1 << v.size()); mask2++) { int sum1 = sum; for(int j = 0; j < v.size(); j++) { if((mask2 >> j & 1) == 1)sum1 -= (1 << v[j]); } if(__builtin_popcount(mask2) & 1) { ans -= dp[sum1]; } else ans += dp[sum1]; } cout << ans << '\n'; } } }
#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...