This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int L, Q; cin >> L >> Q;
int* v = new int[1<<L];
for(int i = 0; i < (1<<L); i++){
char c; cin >> c;
v[i] = c-'0';
}
int *dp1 = new int[1<<L], *dp2 = new int[1<<L];
fill(dp1, dp1+(1<<L), 0);
fill(dp2, dp2+(1<<L), 0);
for(int i = 0; i < (1<<L); i++){
dp1[i]+=v[i];
dp2[((1<<L)-1)^i]+=v[i];
}
for(int j = 0; j < L; j++) for(int i = 0; i < (1<<L); i++) if(i&(1<<j)){
dp1[i]+=dp1[i^(1<<j)];
dp2[i]+=dp2[i^(1<<j)];
}
int L_3 = L/3;
while(Q--){
str s; cin >> s;
int z = 0, o = 0, u = 0;
reverse(s.begin(), s.end());
for(int i = 0; i < L; i++){
if(s[i] == '0') z+=(1<<i);
if(s[i] == '1') o+=(1<<i);
if(s[i] == '?') u+=(1<<i);
}
int ans = 0;
if(__builtin_popcount(u) <= L_3){
ans+=v[o];
for(int i = u; i > 0; i = (i-1)&u) ans+=v[i|o];
}
else if(__builtin_popcount(o) <= L_3){
ans+=dp1[u]*(__builtin_popcount(o)&1?-1:1);
for(int i = o; i > 0; i = (i-1)&o)
ans+=dp1[i|u]*((__builtin_popcount(o)-__builtin_popcount(i))&1?-1:1);
}
else{
ans+=dp2[u]*(__builtin_popcount(z)&1?-1:1);
for(int i = z; i > 0; i = (i-1)&z)
ans+=dp2[i|u]*((__builtin_popcount(z)-__builtin_popcount(i))&1?-1:1);
}
cout << ans << "\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |