#include<iostream>
using namespace std;
const int MAXN = (1<<20) + 10;
int n, q, a, b, c, sol, mask;
char l[30], cc;
int val[MAXN], sum0[MAXN], sum1[MAXN], pc[MAXN];
void precompute () {
for (int i=0; i<(1<<n); i++) {
pc[i] = __builtin_popcount(i);
sum0[i] = val[i];
sum1[i] = val[i ^ ((1<<n) - 1)];
}
for (int i=0; i<n; i++) {
for (int j=0; j<(1<<n); j++) {
if (j & (1<<i)) sum0[j] += sum0[j ^ (1<<i)];
if (j & (1<<i)) sum1[j] += sum1[j ^ (1<<i)];
}
}
}
#define pcc(x) putchar_unlocked(x);
inline void writeInt (int n)
{
int N = n, rev, count = 0;
rev = N;
if (N == 0) { pcc('0'); pcc('\n'); return ;}
while ((rev % 10) == 0) { count++; rev /= 10;} //obtain the count of the number of 0s
rev = 0;
while (N != 0) { rev = (rev<<3) + (rev<<1) + N % 10; N /= 10;} //store reverse of N in rev
while (rev != 0) { pcc(rev % 10 + '0'); rev /= 10;}
while (count--) pcc('0');
}
int main () {
cin >> n >> q;
for (int i=0; i<(1<<n); i++) {
do {
cc = getchar();
} while (!((cc>='0' && cc<='9') || cc=='?'));
val[i] = cc - '0';
}
precompute();
for (int tc=0; tc<q; tc++) {
a = b = c = 0;
for (int i=0; i<n; i++) {
do {
cc = getchar();
} while (!((cc>='0' && cc<='9') || cc=='?'));
l[i] = cc;
if (l[i] == '?') {
a ^= (1<<(n-1-i));
} else if (l[i] == '0') {
b ^= (1<<(n-1-i));
} else {
c ^= (1<<(n-1-i));
}
}
sol = 0, mask = 0;
if (pc[a] <= n/3) {
do {
sol += val[mask | c];
} while (mask = (mask-a) & a);
} else if (pc[b] <= n/3) {
do {
if (pc[mask | a] & 1) {
sol -= sum1[mask | a];
} else {
sol += sum1[mask | a];
}
} while (mask = (mask-b) & b);
if (sol < 0) sol = -sol;
} else {
do {
if (pc[mask | a] & 1) {
sol -= sum0[mask | a];
} else {
sol += sum0[mask | a];
}
} while (mask = (mask-c) & c);
if (sol < 0) sol = -sol;
}
writeInt(sol);
putchar('\n');
}
return 0;
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:65:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} while (mask = (mask-a) & a);
~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:73:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} while (mask = (mask-b) & b);
~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:82:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} while (mask = (mask-c) & c);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Correct |
4 ms |
548 KB |
Output is correct |
| 4 |
Correct |
5 ms |
592 KB |
Output is correct |
| 5 |
Correct |
4 ms |
592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
3 ms |
620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
660 KB |
Output is correct |
| 10 |
Correct |
3 ms |
788 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Correct |
4 ms |
548 KB |
Output is correct |
| 4 |
Correct |
5 ms |
592 KB |
Output is correct |
| 5 |
Correct |
4 ms |
592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
3 ms |
620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
660 KB |
Output is correct |
| 10 |
Correct |
3 ms |
788 KB |
Output is correct |
| 11 |
Correct |
273 ms |
6524 KB |
Output is correct |
| 12 |
Correct |
279 ms |
6524 KB |
Output is correct |
| 13 |
Correct |
246 ms |
6524 KB |
Output is correct |
| 14 |
Correct |
297 ms |
6524 KB |
Output is correct |
| 15 |
Correct |
254 ms |
6872 KB |
Output is correct |
| 16 |
Correct |
262 ms |
6872 KB |
Output is correct |
| 17 |
Correct |
266 ms |
6872 KB |
Output is correct |
| 18 |
Correct |
191 ms |
8576 KB |
Output is correct |
| 19 |
Correct |
224 ms |
8576 KB |
Output is correct |
| 20 |
Correct |
265 ms |
8576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Correct |
4 ms |
548 KB |
Output is correct |
| 4 |
Correct |
5 ms |
592 KB |
Output is correct |
| 5 |
Correct |
4 ms |
592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
3 ms |
620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
660 KB |
Output is correct |
| 10 |
Correct |
3 ms |
788 KB |
Output is correct |
| 11 |
Correct |
273 ms |
6524 KB |
Output is correct |
| 12 |
Correct |
279 ms |
6524 KB |
Output is correct |
| 13 |
Correct |
246 ms |
6524 KB |
Output is correct |
| 14 |
Correct |
297 ms |
6524 KB |
Output is correct |
| 15 |
Correct |
254 ms |
6872 KB |
Output is correct |
| 16 |
Correct |
262 ms |
6872 KB |
Output is correct |
| 17 |
Correct |
266 ms |
6872 KB |
Output is correct |
| 18 |
Correct |
191 ms |
8576 KB |
Output is correct |
| 19 |
Correct |
224 ms |
8576 KB |
Output is correct |
| 20 |
Correct |
265 ms |
8576 KB |
Output is correct |
| 21 |
Correct |
313 ms |
8576 KB |
Output is correct |
| 22 |
Correct |
336 ms |
8576 KB |
Output is correct |
| 23 |
Correct |
416 ms |
8576 KB |
Output is correct |
| 24 |
Correct |
392 ms |
8576 KB |
Output is correct |
| 25 |
Correct |
398 ms |
8824 KB |
Output is correct |
| 26 |
Correct |
382 ms |
8824 KB |
Output is correct |
| 27 |
Correct |
427 ms |
8824 KB |
Output is correct |
| 28 |
Correct |
245 ms |
9692 KB |
Output is correct |
| 29 |
Correct |
273 ms |
9692 KB |
Output is correct |
| 30 |
Correct |
317 ms |
9692 KB |
Output is correct |
| 31 |
Correct |
346 ms |
9692 KB |
Output is correct |
| 32 |
Correct |
454 ms |
9692 KB |
Output is correct |
| 33 |
Correct |
265 ms |
9692 KB |
Output is correct |
| 34 |
Correct |
321 ms |
9692 KB |
Output is correct |
| 35 |
Correct |
372 ms |
21816 KB |
Output is correct |
| 36 |
Correct |
225 ms |
34012 KB |
Output is correct |
| 37 |
Correct |
277 ms |
49800 KB |
Output is correct |
| 38 |
Correct |
273 ms |
61628 KB |
Output is correct |
| 39 |
Runtime error |
360 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 40 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Correct |
4 ms |
548 KB |
Output is correct |
| 4 |
Correct |
5 ms |
592 KB |
Output is correct |
| 5 |
Correct |
4 ms |
592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
3 ms |
620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
660 KB |
Output is correct |
| 10 |
Correct |
3 ms |
788 KB |
Output is correct |
| 11 |
Runtime error |
106 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Correct |
4 ms |
548 KB |
Output is correct |
| 4 |
Correct |
5 ms |
592 KB |
Output is correct |
| 5 |
Correct |
4 ms |
592 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
3 ms |
620 KB |
Output is correct |
| 8 |
Correct |
3 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
660 KB |
Output is correct |
| 10 |
Correct |
3 ms |
788 KB |
Output is correct |
| 11 |
Correct |
273 ms |
6524 KB |
Output is correct |
| 12 |
Correct |
279 ms |
6524 KB |
Output is correct |
| 13 |
Correct |
246 ms |
6524 KB |
Output is correct |
| 14 |
Correct |
297 ms |
6524 KB |
Output is correct |
| 15 |
Correct |
254 ms |
6872 KB |
Output is correct |
| 16 |
Correct |
262 ms |
6872 KB |
Output is correct |
| 17 |
Correct |
266 ms |
6872 KB |
Output is correct |
| 18 |
Correct |
191 ms |
8576 KB |
Output is correct |
| 19 |
Correct |
224 ms |
8576 KB |
Output is correct |
| 20 |
Correct |
265 ms |
8576 KB |
Output is correct |
| 21 |
Correct |
313 ms |
8576 KB |
Output is correct |
| 22 |
Correct |
336 ms |
8576 KB |
Output is correct |
| 23 |
Correct |
416 ms |
8576 KB |
Output is correct |
| 24 |
Correct |
392 ms |
8576 KB |
Output is correct |
| 25 |
Correct |
398 ms |
8824 KB |
Output is correct |
| 26 |
Correct |
382 ms |
8824 KB |
Output is correct |
| 27 |
Correct |
427 ms |
8824 KB |
Output is correct |
| 28 |
Correct |
245 ms |
9692 KB |
Output is correct |
| 29 |
Correct |
273 ms |
9692 KB |
Output is correct |
| 30 |
Correct |
317 ms |
9692 KB |
Output is correct |
| 31 |
Correct |
346 ms |
9692 KB |
Output is correct |
| 32 |
Correct |
454 ms |
9692 KB |
Output is correct |
| 33 |
Correct |
265 ms |
9692 KB |
Output is correct |
| 34 |
Correct |
321 ms |
9692 KB |
Output is correct |
| 35 |
Correct |
372 ms |
21816 KB |
Output is correct |
| 36 |
Correct |
225 ms |
34012 KB |
Output is correct |
| 37 |
Correct |
277 ms |
49800 KB |
Output is correct |
| 38 |
Correct |
273 ms |
61628 KB |
Output is correct |
| 39 |
Runtime error |
360 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 40 |
Halted |
0 ms |
0 KB |
- |
