#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
const int maxn = 1e5 + 5;
const int sqrtn = 500;
int super[maxn], sub[maxn];
//sos dp + sqrt-sort technique(pigeonhole principle)
int main(void){
fastio;
int l, q;
cin>>l>>q;
string s;
cin>>s;
for(int i = 0; i < (1 << l); i++) sub[i] = super[i] = s[i] - '0';
for(int i = 0; i < l; i++){
for(int mask = 0; mask < (1 << l); mask++){
if(mask & (1 << i)) sub[mask] += sub[mask ^ (1 << i)];
else super[mask] += super[mask ^ (1 << i)];
}
}
for(int mask = 0; mask < (1 << l); mask++) cout<<sub[mask]<<" "<<super[mask]<<"\n";
while(q--){
string t;
cin>>t;
int cnt0 = 0, cnt1 = 0, cnt2 = 0;
int a = 0, b = 0, c = 0; //a = 0, b = 1, c = 2
for(int i = 0; i < l; i++){
char x = t[i];
if(x == '0') cnt0++, a |= (1 << (l - i - 1));
else if(x == '1') cnt1++, b |= (1 << (l - i - 1));
else cnt2++, c |= (1 << (l - i - 1));
}
int ans = 0;
if(cnt2 <= cnt0 && cnt2 <= cnt1){
for(int mask = c; mask > 0; mask = (mask - 1) & c){
ans += s[mask | b] - '0';
}
ans += s[b] - '0';
}
else if(cnt0 <= cnt1){
for(int mask = a; mask > 0; mask = (mask - 1) & a){
ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * super[mask | b];
}
ans += super[b];
}
else{
for(int mask = b; mask > 0; mask = (mask - 1) & b){
ans += (1 - 2 * (__builtin_popcount(mask) & 1)) * sub[c | (b ^ mask)];
}
ans += sub[c | b];
}
cout<<ans<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
