#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
const int M = 4782969; // 3 ^ 12
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[13], f[M], g[M];
string a;
void prepare() {
for (int i = 0; i < (1 << 14); ++i) {
for (int j = 13; 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 8 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 12 bits
mask3[i] *= 3;
if (s[j] == '1') mask3[i]++;
if (s[j] == '?') mask3[i] += 2;
}
}
prepare();
for (int i = 0; i < 64; ++i) { // first 8 bits
memset(f, 0, sizeof f);
for (int j = 0; j < (1 << max(0, n - 6)); ++j) {
f[to3[j]] += a[j << 6 | i] - '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:54: 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 |
Correct |
1103 ms |
37832 KB |
Output is correct |
2 |
Correct |
1092 ms |
38112 KB |
Output is correct |
3 |
Correct |
1122 ms |
38112 KB |
Output is correct |
4 |
Correct |
1111 ms |
38112 KB |
Output is correct |
5 |
Correct |
1147 ms |
38164 KB |
Output is correct |
6 |
Correct |
1189 ms |
38360 KB |
Output is correct |
7 |
Correct |
1196 ms |
38360 KB |
Output is correct |
8 |
Correct |
1163 ms |
38360 KB |
Output is correct |
9 |
Correct |
1216 ms |
38360 KB |
Output is correct |
10 |
Correct |
1267 ms |
38372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1103 ms |
37832 KB |
Output is correct |
2 |
Correct |
1092 ms |
38112 KB |
Output is correct |
3 |
Correct |
1122 ms |
38112 KB |
Output is correct |
4 |
Correct |
1111 ms |
38112 KB |
Output is correct |
5 |
Correct |
1147 ms |
38164 KB |
Output is correct |
6 |
Correct |
1189 ms |
38360 KB |
Output is correct |
7 |
Correct |
1196 ms |
38360 KB |
Output is correct |
8 |
Correct |
1163 ms |
38360 KB |
Output is correct |
9 |
Correct |
1216 ms |
38360 KB |
Output is correct |
10 |
Correct |
1267 ms |
38372 KB |
Output is correct |
11 |
Correct |
1770 ms |
65536 KB |
Output is correct |
12 |
Correct |
1808 ms |
65536 KB |
Output is correct |
13 |
Correct |
1918 ms |
65536 KB |
Output is correct |
14 |
Correct |
1847 ms |
65536 KB |
Output is correct |
15 |
Execution timed out |
2050 ms |
65536 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1103 ms |
37832 KB |
Output is correct |
2 |
Correct |
1092 ms |
38112 KB |
Output is correct |
3 |
Correct |
1122 ms |
38112 KB |
Output is correct |
4 |
Correct |
1111 ms |
38112 KB |
Output is correct |
5 |
Correct |
1147 ms |
38164 KB |
Output is correct |
6 |
Correct |
1189 ms |
38360 KB |
Output is correct |
7 |
Correct |
1196 ms |
38360 KB |
Output is correct |
8 |
Correct |
1163 ms |
38360 KB |
Output is correct |
9 |
Correct |
1216 ms |
38360 KB |
Output is correct |
10 |
Correct |
1267 ms |
38372 KB |
Output is correct |
11 |
Correct |
1770 ms |
65536 KB |
Output is correct |
12 |
Correct |
1808 ms |
65536 KB |
Output is correct |
13 |
Correct |
1918 ms |
65536 KB |
Output is correct |
14 |
Correct |
1847 ms |
65536 KB |
Output is correct |
15 |
Execution timed out |
2050 ms |
65536 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1103 ms |
37832 KB |
Output is correct |
2 |
Correct |
1092 ms |
38112 KB |
Output is correct |
3 |
Correct |
1122 ms |
38112 KB |
Output is correct |
4 |
Correct |
1111 ms |
38112 KB |
Output is correct |
5 |
Correct |
1147 ms |
38164 KB |
Output is correct |
6 |
Correct |
1189 ms |
38360 KB |
Output is correct |
7 |
Correct |
1196 ms |
38360 KB |
Output is correct |
8 |
Correct |
1163 ms |
38360 KB |
Output is correct |
9 |
Correct |
1216 ms |
38360 KB |
Output is correct |
10 |
Correct |
1267 ms |
38372 KB |
Output is correct |
11 |
Correct |
1255 ms |
65536 KB |
Output is correct |
12 |
Correct |
1194 ms |
65536 KB |
Output is correct |
13 |
Correct |
1256 ms |
65536 KB |
Output is correct |
14 |
Correct |
1223 ms |
65536 KB |
Output is correct |
15 |
Correct |
1192 ms |
65536 KB |
Output is correct |
16 |
Correct |
1192 ms |
65536 KB |
Output is correct |
17 |
Correct |
1165 ms |
65536 KB |
Output is correct |
18 |
Correct |
1204 ms |
65536 KB |
Output is correct |
19 |
Correct |
1152 ms |
65536 KB |
Output is correct |
20 |
Correct |
1180 ms |
65536 KB |
Output is correct |
21 |
Correct |
1209 ms |
65536 KB |
Output is correct |
22 |
Correct |
1198 ms |
65536 KB |
Output is correct |
23 |
Correct |
1196 ms |
65536 KB |
Output is correct |
24 |
Correct |
1186 ms |
65536 KB |
Output is correct |
25 |
Correct |
1195 ms |
65536 KB |
Output is correct |
26 |
Correct |
1262 ms |
65536 KB |
Output is correct |
27 |
Correct |
1207 ms |
65536 KB |
Output is correct |
28 |
Correct |
1169 ms |
65536 KB |
Output is correct |
29 |
Correct |
1213 ms |
65536 KB |
Output is correct |
30 |
Correct |
1249 ms |
65536 KB |
Output is correct |
31 |
Correct |
1247 ms |
65536 KB |
Output is correct |
32 |
Correct |
1245 ms |
65536 KB |
Output is correct |
33 |
Correct |
1154 ms |
65536 KB |
Output is correct |
34 |
Correct |
1156 ms |
65536 KB |
Output is correct |
35 |
Correct |
1168 ms |
65536 KB |
Output is correct |
36 |
Correct |
1278 ms |
65536 KB |
Output is correct |
37 |
Correct |
1226 ms |
65536 KB |
Output is correct |
38 |
Correct |
1214 ms |
65536 KB |
Output is correct |
39 |
Correct |
1191 ms |
65536 KB |
Output is correct |
40 |
Correct |
1151 ms |
65536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1103 ms |
37832 KB |
Output is correct |
2 |
Correct |
1092 ms |
38112 KB |
Output is correct |
3 |
Correct |
1122 ms |
38112 KB |
Output is correct |
4 |
Correct |
1111 ms |
38112 KB |
Output is correct |
5 |
Correct |
1147 ms |
38164 KB |
Output is correct |
6 |
Correct |
1189 ms |
38360 KB |
Output is correct |
7 |
Correct |
1196 ms |
38360 KB |
Output is correct |
8 |
Correct |
1163 ms |
38360 KB |
Output is correct |
9 |
Correct |
1216 ms |
38360 KB |
Output is correct |
10 |
Correct |
1267 ms |
38372 KB |
Output is correct |
11 |
Correct |
1770 ms |
65536 KB |
Output is correct |
12 |
Correct |
1808 ms |
65536 KB |
Output is correct |
13 |
Correct |
1918 ms |
65536 KB |
Output is correct |
14 |
Correct |
1847 ms |
65536 KB |
Output is correct |
15 |
Execution timed out |
2050 ms |
65536 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |