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 F first
#define S second
#define ll long long
#define pii pair<ll,int>
const int mxN = (1 << 20) + 5;
const int mod = 1e9 + 7;
using namespace std;
int sos[mxN][2][2];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,q;
cin >>n>>q;
string s;
cin>>s;
for(int i = 0;i < n;i++){
for(int mask = 0;mask < (1 << n);mask++){
if(!i){
sos[mask][0][0] = s[mask] - '0';
if((mask &1)) sos[mask][0][0] += s[mask - 1] - '0';
sos[mask][0][1] = s[mask] - '0';
if((mask &1) == 0) sos[mask][0][1] += s[mask + 1] - '0';
continue;
}
sos[mask][i &1][0] = sos[mask][(i - 1)&1][0];
sos[mask][i &1][1] = sos[mask][(i - 1)&1][1];
if(mask >> i & 1) sos[mask][(i)&1][0] += sos[mask - (1 << i)][(i - 1)&1][0];
else sos[mask][i &1][1] += sos[mask + (1 << i)][(i - 1)&1][1];
}
}
while(q--){
string a;
cin >>a;
reverse(a.begin(),a.end());
int Qcnt = 0, Ocnt = 0, Icnt = 0;
for(auto x : a){
if(x == '?') Qcnt++;
else if(x == '1') Icnt++;
else Ocnt++;
}
int ans = 0;
if(min({Qcnt,Ocnt,Icnt}) == Qcnt){
// printf("? small\n");
int m1 = 0,m2 = 0,m3 = 0;
int i = 0;
for(auto x : a){
if(x == '1') m1 += (1 << i);
if(x == '?') m2 += (1 << i);
i++;
}
m3 = m2;
while(m3 > 0){
ans += s[m3 + m1] - '0';
m3 = (m3 - 1) & m2;
}
ans += s[m1] - '0';
}else if(min({Qcnt,Ocnt,Icnt}) == Icnt){
// printf("1 small\n");
int m1 = 0,m2 = 0,m3 = 0;
int i = 0;
for(auto x : a){
if(x == '?') m1 += (1 << i);
if(x == '1') m2 += (1 << i);
i++;
}
m3 = m2;
while(m3 > 0){
if(((Icnt + Qcnt) &1) == (__builtin_popcount(m3 + m1) & 1)) ans += sos[m3 + m1][(n - 1) & 1][0];
else ans -= sos[m3 + m1][(n - 1) & 1][0];
m3 = (m3 - 1) & m2;
}
if(((Icnt + Qcnt) & 1) == (__builtin_popcount(m1) & 1)) ans += sos[m1][(n - 1) & 1][0];
else ans -= sos[m1][(n - 1) & 1][0];
}else{
// printf("0 small\n");
int m1 = 0,m2 = 0,m3 = 0;
int i = 0;
for(auto x : a){
if(x == '1') m1 += (1 << i);
if(x == '0') m2 += (1 << i);
i++;
}
m3 = m2;
while(m3 > 0){
if((Icnt & 1) == (__builtin_popcount(m3 + m1) &1)) ans += sos[m3 + m1][(n - 1) & 1][1];
else ans -= sos[m3 + m1][(n - 1) & 1][1];
m3 = (m3 - 1) & m2;
}
if((Icnt & 1) == (__builtin_popcount(m1) &1)) ans += sos[m1][(n - 1) & 1][1];
else ans -= sos[m1][(n - 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... |