import java.io.*; import java.util.*;
public class snake_escaping{
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
}
public static class Pair implements Comparable<Pair>{
int vtx; int val;
public Pair(int a, int b){
this.vtx=a; this.val=b;
}
public int compareTo(Pair other){
if(this.val<other.val)return -1;
if(this.val>other.val)return 1;
if(this.vtx<other.vtx)return -1;
return 1;
}
}
static int MOD=998244353;
public static void main(String[] args){
FastReader br=new FastReader();
int L=br.nextInt(); int Q=br.nextInt();
final int[] S=new int[1<<L]; final int[] sup=new int[1<<L]; final int[] sub=new int[1<<L];
final int[] btcnt=new int[1<<L];
String s=br.next();
for(int i=0; i<(1<<L); i++){
S[i]=(int) s.charAt(i)-'0'; sup[i]=sub[i]=S[i];
btcnt[i]=Integer.bitCount(i);
}
//SOS DP!!
for(int b=0; b<L; b++){
for(int m=0;m<(1<<L); m++){
if(((m>>>b)&1) ==0){
sup[m]+=sup[m^(1<<b)];
}else{
sub[m]+=sub[m^(1<<b)];
}
}
}
System.out.println(Arrays.toString(sub));
System.out.println(Arrays.toString(sup));
StringBuilder sb=new StringBuilder();
//sb can have a lot of memory
int A; int B; int C;
int ca; int cb; int cc; long ans;
for(int i=0;i<Q;i++){
s=br.next(); A=0; B=0; C=0;
ca=0; cb=0; cc=0; ans=0;
for(int j=0;j<L;j++){
if(s.charAt(j)=='0'){A|=(1<<(L-j-1)); ca++;}
else if(s.charAt(j)=='1') {B|=(1<<(L-j-1)); cb++;}
else {C|=(1<<(L-j-1)); cc++;}
}
//System.out.println(ca+" "+cb+" "+cc);
if(ca<=cb && ca<=cc){
for(int m=A; m!=0; m=(m-1)&A){
ans+=(1-2*((btcnt[m])&1))*sup[B|m];
}
ans+=sup[B];
}else if(cb<=ca && cb<=cc){
for(int m=B; m!=0; m=(m-1)&B){
ans+=(1-2*((btcnt[m])&1))*sub[C|(B^m)];
}
ans+=sub[C|B];
}else{
for(int m=C; m!=0; m=(m-1)&C){
ans+=S[m|B];
}
//System.out.println(A+" "+B);
ans+=S[B];
}
sb.append(ans).append("\n");
if((i&((1<<17)-1))==0){
System.out.println(sb.toString());
sb=new StringBuilder();
}
}
System.out.println(sb.toString());
}
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
10644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
10644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
10644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
10644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
10644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
