#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ryan bear
#define sq(X) ((X)*(X))
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
#define unq(V) (V).erase(unique(all(V)), (V).end())
using namespace std;
typedef long long ll;
typedef vector<ll> vlm;
typedef vector<int> vim;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
int L, Q;
int ar[(1<<20)]; char AR[(1<<20)];
int a1[(1<<20)], a2[(1<<20)], a3[(1<<20)]; //01, 0?, ?1
char s[20];
pii stk[(1<<20)];
vim bs;
inline void f1() { //a1
int cnt=0, x=0, ans=0;
for (int i=0; i<L; i++) if (s[i]=='1') x|=(1<<i);
bs.clear();
for (int i=0; i<L; i++) if (s[i]=='?') { cnt++; bs.eb(i); }
stk[0]=pii(x, 0);
int tp=1, e=1;
for (int i=0; i<cnt; i++) {
for (int j=0; j<e; j++) stk[tp++]=pii(stk[j].fi^bs[i], 0);
e=tp;
}
for (int i=0; i<e; i++) ans+=a1[stk[i].fi];
printf("%d\n", ans);
}
inline void f2() { //a2
int cnt=0, x=0, ans=0;
for (int i=0; i<L; i++) if (s[i]=='?'||s[i]=='1') x|=(1<<i);
bs.clear();
for (int i=0; i<L; i++) if (s[i]=='1') { cnt++; bs.eb(i); }
stk[0]=pii(x, 0);
int tp=1, e=1;
for (int i=0; i<cnt; i++) {
for (int j=0; j<e; j++) stk[tp++]=pii(stk[j].fi^bs[i], stk[j].se+1);
e=tp;
}
for (int i=0; i<e; i++) ans+=a2[stk[i].fi]*(stk[i].se%2?-1:1);
printf("%d\n", ans);
}
inline void f3() { //a3
int cnt=0, x=0, ans=0;
for (int i=0; i<L; i++) if (s[i]=='1') x|=(1<<i);
bs.clear();
for (int i=0; i<L; i++) if (s[i]=='0') { cnt++; bs.eb(i); }
stk[0]=pii(x, 0);
int tp=1, e=1;
for (int i=0; i<cnt; i++) {
for (int j=0; j<e; j++) stk[tp++]=pii(stk[j].fi^bs[i], stk[j].se+1);
e=tp;
}
for (int i=0; i<e; i++) ans+=a3[stk[i].fi]*(stk[i].se%2?-1:1);
printf("%d\n", ans);
}
int main() {
scanf("%d %d", &L, &Q);
scanf("%s", AR);
for (int i=0; i<(1<<L); i++) ar[i]=AR[i]-'0';
for (int i=0; i<(1<<L); i++) a1[i]=ar[i];
for (int i=0; i<(1<<L); i++) {
bs.clear();
int im, cnt=0;
for (int j=0; j<L; j++) if (!(i&(1<<j))) {
cnt++;
bs.eb(j);
}
int e=1, tp=1;
stk[0]=pii(i, 0);
for (int j=0; j<cnt; j++) {
for (int k=0; k<e; k++) stk[tp++]=pii(stk[k].fi^(1<<bs[j]), 0);
e=tp;
}
for (int j=0; j<e; j++) a2[stk[j].fi]+=ar[i];
}
for (int i=0; i<(1<<L); i++) {
bs.clear();
int im, cnt=0;
for (int j=0; j<L; j++) if (i&(1<<j)) {
cnt++;
bs.eb(j);
}
int e, tp=1;
stk[0]=pii(i, 0);
for (int j=0; j<cnt; j++) {
for (int k=0; k<e; k++) stk[tp++]=pii(stk[k].fi^(1<<bs[j]), 0);
e=tp;
}
for (int j=0; j<e; j++) a3[stk[j].fi]+=ar[i];
}
while (Q--) {
scanf("%s", s);
int c0=0, c1=0, cq=0;
for (int i=0; i<L; i++) (s[i]=='0'?c0:s[i]=='1'?c1:cq)++;
reverse(s, s+L);
if (c0<=c1&&c0<=cq) f2();
else if (c1<=c0&&c1<=cq) f3();
else f1();
}
return 0;
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:75:7: warning: unused variable 'im' [-Wunused-variable]
int im, cnt=0;
^~
snake_escaping.cpp:90:7: warning: unused variable 'im' [-Wunused-variable]
int im, cnt=0;
^~
snake_escaping.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &L, &Q);
~~~~~^~~~~~~~~~~~~~~~~
snake_escaping.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", AR);
~~~~~^~~~~~~~~~
snake_escaping.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s);
~~~~~^~~~~~~~~
snake_escaping.cpp:95:7: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
int e, tp=1;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
604 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
