#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <map>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
char all[1148576];
char tt[25];
int con1[2][1100005];
int con2[2][1100005];
int ans=0;
int N;
queue < pair < pair < int , int > , int > > BFS;
void F(int x,int y,int z)
{
if(x==N)
{
if(z%2==0) ans+=con1[N%2][y];
else ans-=con1[N%2][y];
return;
}
if(tt[x]=='1')
{
F(x+1,y+(1<<(N-x-1)),z);
F(x+1,y,z+1);
}
else if(tt[x]=='0') F(x+1,y,z);
else F(x+1,y+(1<<(N-x-1)),z);
}
void F2(int x,int y)
{
if(x==N)
{
ans+=(all[y]-'0');
return;
}
if(tt[x]=='?')
{
F2(x+1,y);
F2(x+1,y+(1<<(N-x-1)));
}
else F2(x+1,y+(1<<(N-x-1))*(tt[x]-'0'));
}
void F3(int x,int y,int z)
{
if(x==N)
{
if(z%2==0) ans+=con2[N%2][y];
else ans-=con2[N%2][y];
return;
}
if(tt[x]=='0')
{
F3(x+1,y+(1<<(N-x-1)),z+1);
F3(x+1,y,z);
}
else if(tt[x]=='1') F3(x+1,y+(1<<(N-x-1)),z);
else F3(x+1,y,z);
}
int main()
{
//freopen("05-05.txt","rt",stdin);
//freopen("tt.txt","w+t",stdout);
int M,i,j,ok,a,b,c,x,y,z;
scanf("%d %d",&N,&M);
scanf("%s",all);
for(i=0;i<(1<<N);i++) con2[0][i]=con1[0][i]=all[i]-'0';
for(i=0;i<N;i++)
{
for(j=0;j<(1<<N);j++)
{
con1[1-i%2][j]=con1[i%2][j];
con2[1-i%2][j]=con2[i%2][j];
if(j&(1<<i)) con1[1-i%2][j]+=con1[i%2][j-(1<<i)];
else con2[1-i%2][j]+=con2[i%2][j+(1<<i)];
}
}
while(M--)
{
scanf("%s",tt);
ans=0;
a=0;
b=0;
c=0;
for(i=0;i<N;i++)
{
if(tt[i]=='?') a++;
else if(tt[i]=='1') b++;
else c++;
}
if(b<=a&&b<=c)
{
BFS.push(make_pair(make_pair(0,0),0));
while(!BFS.empty())
{
x=BFS.front().first.first;
y=BFS.front().first.second;
z=BFS.front().second;
BFS.pop();
if(x==N)
{
if(z==0) ans+=con1[N%2][y];
else ans-=con1[N%2][y];
continue;
}
if(tt[x]=='1')
{
BFS.push(make_pair(make_pair(x+1,y+(1<<(N-x-1))),z));
BFS.push(make_pair(make_pair(x+1,y),z^1));
}
else if(tt[x]=='0') BFS.push(make_pair(make_pair(x+1,y),z^1));
else BFS.push(make_pair(make_pair(x+1,y+(1<<(N-x-1))),z));
}
}
else if(a<=b&&a<=c) F2(0,0);
else if(c<=b&&c<=a) F3(0,0,0);
printf("%d\n",ans);
}
return 0;
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:71:15: warning: unused variable 'ok' [-Wunused-variable]
71 | int M,i,j,ok,a,b,c,x,y,z;
| ^~
snake_escaping.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
72 | scanf("%d %d",&N,&M);
| ~~~~~^~~~~~~~~~~~~~~
snake_escaping.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%s",all);
| ~~~~~^~~~~~~~~~
snake_escaping.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
90 | scanf("%s",tt);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
