#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
//#define mp make_pair
#define ll long long
//#define int ll
//#define double long double
const ll INF=1e18,N=(1<<20)+5;
int dp[N],dp2[N],a[N];
void solve(){
int n,q;cin>>n>>q;
string s;cin>>s;
for(int i=0;i<(1<<n);i++) a[i]=(s[i]-'0');
for(int i=0;i<(1<<n);i++) dp[i]=dp2[i]=a[i];
for(int i=0;i<n;i++){
for(int mask=0;mask<(1<<n);mask++){
if(mask&(1<<i)) dp[mask]+=dp[mask^(1<<i)];
else dp2[mask]+=dp2[mask^(1<<i)];
}
}
while(q--){
string st;cin>>st;
int z=0,o=0,u=0;
for(int i=0;i<st.size();i++){
if(st[i]=='?') u++;
else if(st[i]=='0') z++;
else o++;
}
int sum=0,ans=0;
vector<int> tmp;
if(u<=6){
reverse(all(st));
for(int i=0;i<n;i++){
if(st[i]=='1') sum+=(1<<i);
if(st[i]=='?') tmp.pb(1<<i);
}
for(int i=0;i<(1<<tmp.size());i++){
int tmpsum=sum;
for(int j=0;j<tmp.size();j++){
if(i&(1<<j)) tmpsum^=tmp[j];
}
ans+=a[tmpsum];
}
cout<<ans<<endl;
}
else if(o<=6){
reverse(all(st));
for(int i=0;i<n;i++){
if(st[i]=='1' || st[i]=='?') sum+=(1<<i);
if(st[i]=='1') tmp.pb(i);
}
for(int i=0;i<(1<<tmp.size());i++){
int tmpsum=sum,c=0;
for(int j=0;j<tmp.size();j++){
if(i&(1<<j)){
tmpsum^=(1<<tmp[j]);
c++;
}
}
if(c%2) ans-=dp[tmpsum];
else ans+=dp[tmpsum];
}
cout<<ans<<endl;
}
else{
reverse(all(st));
for(int i=0;i<n;i++){
if(st[i]=='1') sum+=(1<<i);
if(st[i]=='0') tmp.pb(i);
}
for(int i=0;i<(1<<tmp.size());i++){
int tmpsum=sum,c=0;
for(int j=0;j<tmp.size();j++){
if(!(i&(1<<j))){
tmpsum^=(1<<tmp[j]);
c++;
}
}
if(c%2) ans-=dp2[tmpsum];
else ans+=dp2[tmpsum];
}
cout<<ans<<endl;
}
}
}
signed main(){
ios;
int t=1;//cin>>t;
while(t--)
solve();
}
Compilation message
snake_escaping.cpp: In function 'void solve()':
snake_escaping.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=0;i<st.size();i++){
| ~^~~~~~~~~~
snake_escaping.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int j=0;j<tmp.size();j++){
| ~^~~~~~~~~~~
snake_escaping.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int j=0;j<tmp.size();j++){
| ~^~~~~~~~~~~
snake_escaping.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int j=0;j<tmp.size();j++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4444 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
3 ms |
4444 KB |
Output is correct |
5 |
Correct |
3 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4444 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4444 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
3 ms |
4444 KB |
Output is correct |
5 |
Correct |
3 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4444 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
1670 ms |
16780 KB |
Output is correct |
12 |
Correct |
1636 ms |
16580 KB |
Output is correct |
13 |
Correct |
1480 ms |
15696 KB |
Output is correct |
14 |
Correct |
1530 ms |
15972 KB |
Output is correct |
15 |
Execution timed out |
2033 ms |
16868 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4444 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
3 ms |
4444 KB |
Output is correct |
5 |
Correct |
3 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4444 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
1670 ms |
16780 KB |
Output is correct |
12 |
Correct |
1636 ms |
16580 KB |
Output is correct |
13 |
Correct |
1480 ms |
15696 KB |
Output is correct |
14 |
Correct |
1530 ms |
15972 KB |
Output is correct |
15 |
Execution timed out |
2033 ms |
16868 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4444 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
3 ms |
4444 KB |
Output is correct |
5 |
Correct |
3 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4444 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
98 ms |
15792 KB |
Output is correct |
12 |
Correct |
109 ms |
15868 KB |
Output is correct |
13 |
Correct |
112 ms |
15876 KB |
Output is correct |
14 |
Correct |
149 ms |
15760 KB |
Output is correct |
15 |
Correct |
107 ms |
15796 KB |
Output is correct |
16 |
Correct |
161 ms |
15824 KB |
Output is correct |
17 |
Correct |
140 ms |
15684 KB |
Output is correct |
18 |
Correct |
96 ms |
16100 KB |
Output is correct |
19 |
Correct |
111 ms |
15880 KB |
Output is correct |
20 |
Correct |
100 ms |
15860 KB |
Output is correct |
21 |
Correct |
121 ms |
15956 KB |
Output is correct |
22 |
Correct |
140 ms |
15892 KB |
Output is correct |
23 |
Correct |
116 ms |
15848 KB |
Output is correct |
24 |
Correct |
130 ms |
15800 KB |
Output is correct |
25 |
Correct |
132 ms |
15744 KB |
Output is correct |
26 |
Correct |
85 ms |
15556 KB |
Output is correct |
27 |
Correct |
114 ms |
15812 KB |
Output is correct |
28 |
Correct |
91 ms |
15784 KB |
Output is correct |
29 |
Correct |
113 ms |
15696 KB |
Output is correct |
30 |
Correct |
163 ms |
15884 KB |
Output is correct |
31 |
Correct |
104 ms |
15708 KB |
Output is correct |
32 |
Correct |
146 ms |
15800 KB |
Output is correct |
33 |
Correct |
124 ms |
15784 KB |
Output is correct |
34 |
Correct |
86 ms |
15636 KB |
Output is correct |
35 |
Correct |
112 ms |
15672 KB |
Output is correct |
36 |
Correct |
114 ms |
15876 KB |
Output is correct |
37 |
Correct |
120 ms |
15716 KB |
Output is correct |
38 |
Correct |
139 ms |
15688 KB |
Output is correct |
39 |
Correct |
133 ms |
15864 KB |
Output is correct |
40 |
Correct |
140 ms |
15852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4444 KB |
Output is correct |
2 |
Correct |
3 ms |
4444 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
3 ms |
4444 KB |
Output is correct |
5 |
Correct |
3 ms |
4444 KB |
Output is correct |
6 |
Correct |
3 ms |
4444 KB |
Output is correct |
7 |
Correct |
2 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4444 KB |
Output is correct |
9 |
Correct |
2 ms |
4444 KB |
Output is correct |
10 |
Correct |
2 ms |
4444 KB |
Output is correct |
11 |
Correct |
1670 ms |
16780 KB |
Output is correct |
12 |
Correct |
1636 ms |
16580 KB |
Output is correct |
13 |
Correct |
1480 ms |
15696 KB |
Output is correct |
14 |
Correct |
1530 ms |
15972 KB |
Output is correct |
15 |
Execution timed out |
2033 ms |
16868 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |