#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
const int M = 2000005;
int n, q;
int to3[1 << 14];
int mask2[2][N]; // 0 check and, 1 check or
int mask3[N];
int res[N];
int pw3[12], f[M], g[M];
string a;
void prepare() {
for (int i = 0; i < (1 << 14); ++i) {
for (int j = 12; j >= 0; --j) {
to3[i] *= 3;
if (i >> j & 1) to3[i]++;
}
}
pw3[0] = 1;
for (int i = 1; i < 14; ++i) pw3[i] = 3 * pw3[i - 1];
for (int i = 0; i < M; ++i) {
int cur = i;
g[i] = -1;
for (int j = 0; j < 14; ++j) {
if (cur % 3 == 2) g[i] = j;
cur /= 3;
}
}
}
void calc() {
for (int i = 0; i < M; ++i) {
if (g[i] != -1) {
f[i] += f[i - 2 * pw3[g[i]]];
f[i] += f[i - 1 * pw3[g[i]]];
}
}
}
inline bool check(int mask, int i) {
return (mask & mask2[0][i]) == mask2[0][i] && (mask | mask2[1][i]) == mask2[1][i];
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> q >> a;
for (int i = 0; i < q; ++i) {
string s; cin >> s;
for (int j = max(0, n - 6); j < n; ++j) { // first 6 bits
mask2[0][i] <<= 1, mask2[1][i] <<= 1;
if (s[j] == '1') mask2[0][i]++;
if (s[j] == '?' || s[j] == '1') mask2[1][i]++;
}
for (int j = 0; j < max(0, n - 6); ++j) { // last 14 bits
mask3[i] *= 3;
if (s[j] == '1') mask3[i]++;
if (s[j] == '?') mask3[i] += 2;
}
}
prepare();
for (int i = 0; i < 128; ++i) { // first 6 bits
memset(f, 0, sizeof f);
for (int j = 0; j < (1 << n); ++j) {
if ((j & 127) != i) continue;
f[to3[j >> 6]] += a[j] - '0';
}
calc();
for (int j = 0; j < q; ++j) {
if (!check(i, j)) continue;
res[j] += f[mask3[j]];
}
}
for (int i = 0; i < q; ++i) printf("%d\n", res[i]);
}
Compilation message
snake_escaping.cpp: In function 'void prepare()':
snake_escaping.cpp:24:53: warning: iteration 12u invokes undefined behavior [-Waggressive-loop-optimizations]
for (int i = 1; i < 14; ++i) pw3[i] = 3 * pw3[i - 1];
^
snake_escaping.cpp:24:20: note: containing loop
for (int i = 1; i < 14; ++i) pw3[i] = 3 * pw3[i - 1];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
796 ms |
16248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
796 ms |
16248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
796 ms |
16248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
796 ms |
16248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
796 ms |
16248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
