| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1305997 | dobri_oke | Snake Escaping (JOI18_snake_escaping) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define F first
#define S second
const int N = (1 << 20) + 5, inf = 1e9 + 1, mod = 1e9 + 7;
int n, q, dp[N];
string s;
void solve(){
cin >> n >> q >> s;
for(int i = 0; i < (1 << n); i++){
dp[i] = s[i] - '0';
}
for(int i = 0; i < n; i++){
for(int mask = 0; mask < (1 << n); mask++){
if(((mask >> i) & 1) == 0){
dp[mask] += dp[(mask | (1 << i))];
}
}
}
while(q--){
string d;
cin >> d;
int g = 0, h = 0, f = 0, cnt = 0, cnt2 = 0, sum = 0;
for(int i = 0; i < n; i++){
if(d[n - i - 1] == '1') g += (1 << i);
else if(d[n - i - 1] == '0'){ h += (1 << i); cnt++;}
else{ f += (1 << i); cnt2++;}
}
if(cnt <= cnt2){
for(int mask = h; ; mask = ((mask - 1) & h)){
int i = __builtin_popcount(mask);
if(i % 2 == 1) sum -= dp[(g | mask)];
else sum += dp[(g | mask)];
if(mask == 0) break;
}
}
else{
for(int mask = f; ; mask = ((mask - 1) & f)){
sum += s[(g | mask)] - '0';
if(mask == 0) break;
}
}
cout << sum << '\n';
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("guard.in", "r", stdin);
//freopen("guard.out", "w", stdout);
int tt = 1;
//cin >> tt;
while(tt--) solve();
}