#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
#define ll long long
// #define ll ll
#define f(i,a,b) for(ll i=a;i<b;i++)
// #define mod 1000000007
#define mod 998244353
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf prllf
#define sz(a) (ll)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (ll)1e18
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
// ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
ll binpow(ll a, ll b, ll md){ll res=1;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
using namespace std;
int n,q;
string s;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("gift1.in","r",stdin);
// freopen("gift1.out","w",stdout);
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// #endif
int z=1;
// cin>>z;
while(z--)
{
cin>>n>>q>>s;
int sup[1<<n|1],sub[1<<n|1],cnt[1<<n|1];
for(int mask=0;mask<(1<<n);mask++)
sub[mask]=sup[mask]=(s[mask]-'0'),cnt[mask]=__builtin_popcount(mask);
f(i,0,n)
{
for(int mask=0;mask<(1<<n);mask++)
{
if(mask&(1<<i))
sub[mask]+=sub[mask^(1<<i)];
else
sup[mask]+=sup[mask^(1<<i)];
}
}
while(q--)
{
string str;
cin>>str;
reverse(all(str));
int mask1=0,mask2=0,mask3=0;
f(i,0,n)
{
if(str[i]=='?')
mask1|=(1<<i);
else if(str[i]=='0')
mask2|=(1<<i);
else
mask3|=(1<<i);
}
int ans=0;
if(cnt[mask1]<=cnt[mask2] && cnt[mask1]<=cnt[mask3])
{
for(int submask=mask1;submask>0;submask=((submask-1)&mask1))
ans+=(s[mask3|submask]-'0');
ans+=(s[mask3]-'0');
}
else if(cnt[mask2]<=cnt[mask3] && cnt[mask2]<=cnt[mask1])
{
for(int submask=mask2;submask>0;submask=(mask2&(submask-1)))
ans+=(((cnt[submask]&1)?-1:1)*sup[submask|mask3]);
ans+=sup[mask3];
}
else
{
for(int submask=mask3;submask>0;submask=(mask3&(submask-1)))
ans+=(((cnt[submask]&1)?-1:1)*sub[submask|mask1]);
ans+=sub[mask1];
}
cout<<ans<<"\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
