#include <bits/stdc++.h>
using namespace std;
const int DIM = 20;
char str[1 << DIM | 3], aux[DIM + 2];
int udp[1 << DIM], ddp[1 << DIM], cbit[1 << DIM];
int main(void) {
#ifdef HOME
freopen("snake.in", "r", stdin);
freopen("snake.out", "w", stdout);
#endif
int n, q; cin >> n >> q >> str;
for (int msk = 0; msk < (1 << n); ++msk) {
cbit[msk] = cbit[msk >> 1] + (msk & 1);
udp[msk] = ddp[msk] = str[msk] - '0'; }
for (int b = 0; b < n; ++b) {
for (int msk = 0; msk < (1 << n); ++msk) {
if (msk & (1 << b)) {
udp[msk ^ (1 << b)] += udp[msk]; }
else {
ddp[msk ^ (1 << b)] += ddp[msk]; } } }
while (q--) {
int msk0 = 0, msk1 = 0, mskq = 0;
cin >> aux; reverse(aux, aux + n);
for (int i = 0; i < n; ++i) {
if (aux[i] == '0') { msk0 ^= (1 << i); }
if (aux[i] == '1') { msk1 ^= (1 << i); }
if (aux[i] == '?') { mskq ^= (1 << i); } }
int ans = 0;
if (cbit[mskq] <= -1) {
for (int axm = mskq, nr = (1 << cbit[mskq]); nr; (--axm) &= mskq, --nr) {
ans += str[axm ^ msk1] - '0'; } }
else if (cbit[msk0] <= 7) {
for (int axm = msk0, nr = (1 << cbit[msk0]); nr; (--axm) &= msk0, --nr) {
ans += udp[msk1 ^ axm] * ((cbit[axm] & 1) ? -1 : 1); } }
else if (cbit[msk1] <= 7) {
for (int axm = msk1, nr = (1 << cbit[msk1]); nr; (--axm) &= msk1, --nr) {
ans += ddp[mskq ^ msk1 ^ axm] * ((cbit[axm] & 1) ? -1 : 1); } }
cout << ans << "\n"; }
return 0; }
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Execution timed out |
2029 ms |
4508 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Execution timed out |
2029 ms |
4508 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Correct |
186 ms |
13976 KB |
Output is correct |
| 12 |
Correct |
213 ms |
14048 KB |
Output is correct |
| 13 |
Incorrect |
235 ms |
13972 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
4 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
384 KB |
Output is correct |
| 10 |
Correct |
5 ms |
384 KB |
Output is correct |
| 11 |
Execution timed out |
2029 ms |
4508 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
