#include<iostream>
using namespace std;
const int MAXN = (1<<20) + 10;
int n, q, a, b, c, sol, mask, N, rev, count, i, j, tc;
char l[30], cc;
int val[MAXN], sum0[MAXN], sum1[MAXN], pc[MAXN];
void precompute () {
for (i=0; i<(1<<n); i++) {
pc[i] = pc[i - (i&-i)]+1;
sum0[i] = val[i];
sum1[i] = val[i ^ ((1<<n) - 1)];
}
for (i=0; i<n; i++) {
for (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(x);
int main () {
cin >> n >> q;
do {
cc = getchar();
} while (!(cc>='0' && cc<='9'));
for (i=0; i<(1<<n); i++) {
if (i>0) {
cc = getchar();
}
val[i] = cc - '0';
}
precompute();
for (tc=0; tc<q; tc++) {
a = b = c = 0;
do {
cc = getchar();
} while (!(cc=='0' || cc=='1' || cc=='?'));
for (i=0; i<n; i++) {
if (i>0) cc = getchar();
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] <= pc[b] && pc[a] <= pc[c]) {
for (mask = a; ; mask = (mask - 1) & a) {
sol += val[mask | c];
if (!mask) break;
}
} else if (pc[b] <= pc[a] && pc[b] <= pc[c]) {
for (mask = b; ; mask = (mask-1) & b) {
rev = mask | a;
if (pc[rev] & 1) {
sol -= sum1[rev];
} else {
sol += sum1[rev];
}
if (!mask) break;
}
if (sol < 0) sol = -sol;
} else {
for (mask = c; ; mask = (mask - 1) & c) {
rev = mask | a;
if (pc[rev] & 1) {
sol -= sum0[rev];
} else {
sol += sum0[rev];
}
if (!mask) break;
}
if (sol < 0) sol = -sol;
}
N = sol, rev, count = 0;
rev = N;
if (N == 0) { pcc('0'); putchar('\n'); continue ;}
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');
putchar('\n');
}
return 0;
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:84:31: warning: right operand of comma operator has no effect [-Wunused-value]
N = sol, rev, count = 0;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Correct |
3 ms |
488 KB |
Output is correct |
| 6 |
Correct |
3 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
544 KB |
Output is correct |
| 8 |
Correct |
2 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Correct |
3 ms |
488 KB |
Output is correct |
| 6 |
Correct |
3 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
544 KB |
Output is correct |
| 8 |
Correct |
2 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
263 ms |
4624 KB |
Output is correct |
| 12 |
Correct |
267 ms |
4624 KB |
Output is correct |
| 13 |
Correct |
324 ms |
4624 KB |
Output is correct |
| 14 |
Correct |
257 ms |
4624 KB |
Output is correct |
| 15 |
Correct |
290 ms |
4624 KB |
Output is correct |
| 16 |
Correct |
323 ms |
4624 KB |
Output is correct |
| 17 |
Correct |
291 ms |
4624 KB |
Output is correct |
| 18 |
Correct |
201 ms |
5548 KB |
Output is correct |
| 19 |
Correct |
209 ms |
5548 KB |
Output is correct |
| 20 |
Correct |
246 ms |
5548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Correct |
3 ms |
488 KB |
Output is correct |
| 6 |
Correct |
3 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
544 KB |
Output is correct |
| 8 |
Correct |
2 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
263 ms |
4624 KB |
Output is correct |
| 12 |
Correct |
267 ms |
4624 KB |
Output is correct |
| 13 |
Correct |
324 ms |
4624 KB |
Output is correct |
| 14 |
Correct |
257 ms |
4624 KB |
Output is correct |
| 15 |
Correct |
290 ms |
4624 KB |
Output is correct |
| 16 |
Correct |
323 ms |
4624 KB |
Output is correct |
| 17 |
Correct |
291 ms |
4624 KB |
Output is correct |
| 18 |
Correct |
201 ms |
5548 KB |
Output is correct |
| 19 |
Correct |
209 ms |
5548 KB |
Output is correct |
| 20 |
Correct |
246 ms |
5548 KB |
Output is correct |
| 21 |
Correct |
342 ms |
5548 KB |
Output is correct |
| 22 |
Correct |
382 ms |
5548 KB |
Output is correct |
| 23 |
Correct |
353 ms |
5548 KB |
Output is correct |
| 24 |
Correct |
380 ms |
5548 KB |
Output is correct |
| 25 |
Correct |
353 ms |
5676 KB |
Output is correct |
| 26 |
Correct |
412 ms |
5676 KB |
Output is correct |
| 27 |
Correct |
404 ms |
5676 KB |
Output is correct |
| 28 |
Correct |
335 ms |
6684 KB |
Output is correct |
| 29 |
Correct |
417 ms |
6684 KB |
Output is correct |
| 30 |
Correct |
354 ms |
6684 KB |
Output is correct |
| 31 |
Correct |
408 ms |
6684 KB |
Output is correct |
| 32 |
Correct |
375 ms |
6684 KB |
Output is correct |
| 33 |
Correct |
308 ms |
6684 KB |
Output is correct |
| 34 |
Correct |
355 ms |
6684 KB |
Output is correct |
| 35 |
Correct |
337 ms |
6684 KB |
Output is correct |
| 36 |
Correct |
226 ms |
6684 KB |
Output is correct |
| 37 |
Correct |
342 ms |
6684 KB |
Output is correct |
| 38 |
Correct |
313 ms |
6684 KB |
Output is correct |
| 39 |
Correct |
378 ms |
6684 KB |
Output is correct |
| 40 |
Correct |
345 ms |
6684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Correct |
3 ms |
488 KB |
Output is correct |
| 6 |
Correct |
3 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
544 KB |
Output is correct |
| 8 |
Correct |
2 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
89 ms |
17324 KB |
Output is correct |
| 12 |
Correct |
89 ms |
17324 KB |
Output is correct |
| 13 |
Correct |
99 ms |
17324 KB |
Output is correct |
| 14 |
Correct |
171 ms |
17324 KB |
Output is correct |
| 15 |
Correct |
120 ms |
17456 KB |
Output is correct |
| 16 |
Correct |
176 ms |
17456 KB |
Output is correct |
| 17 |
Correct |
144 ms |
17456 KB |
Output is correct |
| 18 |
Correct |
107 ms |
17488 KB |
Output is correct |
| 19 |
Correct |
96 ms |
17488 KB |
Output is correct |
| 20 |
Correct |
99 ms |
17488 KB |
Output is correct |
| 21 |
Correct |
129 ms |
17488 KB |
Output is correct |
| 22 |
Correct |
166 ms |
17488 KB |
Output is correct |
| 23 |
Correct |
102 ms |
17488 KB |
Output is correct |
| 24 |
Correct |
128 ms |
17488 KB |
Output is correct |
| 25 |
Correct |
172 ms |
17488 KB |
Output is correct |
| 26 |
Correct |
86 ms |
17488 KB |
Output is correct |
| 27 |
Correct |
102 ms |
17488 KB |
Output is correct |
| 28 |
Correct |
103 ms |
17488 KB |
Output is correct |
| 29 |
Correct |
113 ms |
17488 KB |
Output is correct |
| 30 |
Correct |
128 ms |
17488 KB |
Output is correct |
| 31 |
Correct |
97 ms |
17488 KB |
Output is correct |
| 32 |
Correct |
144 ms |
17488 KB |
Output is correct |
| 33 |
Correct |
147 ms |
17488 KB |
Output is correct |
| 34 |
Correct |
82 ms |
17488 KB |
Output is correct |
| 35 |
Correct |
104 ms |
17488 KB |
Output is correct |
| 36 |
Correct |
129 ms |
17488 KB |
Output is correct |
| 37 |
Correct |
97 ms |
17488 KB |
Output is correct |
| 38 |
Correct |
114 ms |
17488 KB |
Output is correct |
| 39 |
Correct |
109 ms |
17488 KB |
Output is correct |
| 40 |
Correct |
111 ms |
17488 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
440 KB |
Output is correct |
| 4 |
Correct |
3 ms |
488 KB |
Output is correct |
| 5 |
Correct |
3 ms |
488 KB |
Output is correct |
| 6 |
Correct |
3 ms |
544 KB |
Output is correct |
| 7 |
Correct |
2 ms |
544 KB |
Output is correct |
| 8 |
Correct |
2 ms |
640 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
263 ms |
4624 KB |
Output is correct |
| 12 |
Correct |
267 ms |
4624 KB |
Output is correct |
| 13 |
Correct |
324 ms |
4624 KB |
Output is correct |
| 14 |
Correct |
257 ms |
4624 KB |
Output is correct |
| 15 |
Correct |
290 ms |
4624 KB |
Output is correct |
| 16 |
Correct |
323 ms |
4624 KB |
Output is correct |
| 17 |
Correct |
291 ms |
4624 KB |
Output is correct |
| 18 |
Correct |
201 ms |
5548 KB |
Output is correct |
| 19 |
Correct |
209 ms |
5548 KB |
Output is correct |
| 20 |
Correct |
246 ms |
5548 KB |
Output is correct |
| 21 |
Correct |
342 ms |
5548 KB |
Output is correct |
| 22 |
Correct |
382 ms |
5548 KB |
Output is correct |
| 23 |
Correct |
353 ms |
5548 KB |
Output is correct |
| 24 |
Correct |
380 ms |
5548 KB |
Output is correct |
| 25 |
Correct |
353 ms |
5676 KB |
Output is correct |
| 26 |
Correct |
412 ms |
5676 KB |
Output is correct |
| 27 |
Correct |
404 ms |
5676 KB |
Output is correct |
| 28 |
Correct |
335 ms |
6684 KB |
Output is correct |
| 29 |
Correct |
417 ms |
6684 KB |
Output is correct |
| 30 |
Correct |
354 ms |
6684 KB |
Output is correct |
| 31 |
Correct |
408 ms |
6684 KB |
Output is correct |
| 32 |
Correct |
375 ms |
6684 KB |
Output is correct |
| 33 |
Correct |
308 ms |
6684 KB |
Output is correct |
| 34 |
Correct |
355 ms |
6684 KB |
Output is correct |
| 35 |
Correct |
337 ms |
6684 KB |
Output is correct |
| 36 |
Correct |
226 ms |
6684 KB |
Output is correct |
| 37 |
Correct |
342 ms |
6684 KB |
Output is correct |
| 38 |
Correct |
313 ms |
6684 KB |
Output is correct |
| 39 |
Correct |
378 ms |
6684 KB |
Output is correct |
| 40 |
Correct |
345 ms |
6684 KB |
Output is correct |
| 41 |
Correct |
89 ms |
17324 KB |
Output is correct |
| 42 |
Correct |
89 ms |
17324 KB |
Output is correct |
| 43 |
Correct |
99 ms |
17324 KB |
Output is correct |
| 44 |
Correct |
171 ms |
17324 KB |
Output is correct |
| 45 |
Correct |
120 ms |
17456 KB |
Output is correct |
| 46 |
Correct |
176 ms |
17456 KB |
Output is correct |
| 47 |
Correct |
144 ms |
17456 KB |
Output is correct |
| 48 |
Correct |
107 ms |
17488 KB |
Output is correct |
| 49 |
Correct |
96 ms |
17488 KB |
Output is correct |
| 50 |
Correct |
99 ms |
17488 KB |
Output is correct |
| 51 |
Correct |
129 ms |
17488 KB |
Output is correct |
| 52 |
Correct |
166 ms |
17488 KB |
Output is correct |
| 53 |
Correct |
102 ms |
17488 KB |
Output is correct |
| 54 |
Correct |
128 ms |
17488 KB |
Output is correct |
| 55 |
Correct |
172 ms |
17488 KB |
Output is correct |
| 56 |
Correct |
86 ms |
17488 KB |
Output is correct |
| 57 |
Correct |
102 ms |
17488 KB |
Output is correct |
| 58 |
Correct |
103 ms |
17488 KB |
Output is correct |
| 59 |
Correct |
113 ms |
17488 KB |
Output is correct |
| 60 |
Correct |
128 ms |
17488 KB |
Output is correct |
| 61 |
Correct |
97 ms |
17488 KB |
Output is correct |
| 62 |
Correct |
144 ms |
17488 KB |
Output is correct |
| 63 |
Correct |
147 ms |
17488 KB |
Output is correct |
| 64 |
Correct |
82 ms |
17488 KB |
Output is correct |
| 65 |
Correct |
104 ms |
17488 KB |
Output is correct |
| 66 |
Correct |
129 ms |
17488 KB |
Output is correct |
| 67 |
Correct |
97 ms |
17488 KB |
Output is correct |
| 68 |
Correct |
114 ms |
17488 KB |
Output is correct |
| 69 |
Correct |
109 ms |
17488 KB |
Output is correct |
| 70 |
Correct |
111 ms |
17488 KB |
Output is correct |
| 71 |
Correct |
629 ms |
21932 KB |
Output is correct |
| 72 |
Correct |
676 ms |
22184 KB |
Output is correct |
| 73 |
Correct |
974 ms |
22184 KB |
Output is correct |
| 74 |
Correct |
1402 ms |
22184 KB |
Output is correct |
| 75 |
Correct |
894 ms |
22980 KB |
Output is correct |
| 76 |
Correct |
1404 ms |
22980 KB |
Output is correct |
| 77 |
Correct |
1350 ms |
22980 KB |
Output is correct |
| 78 |
Correct |
538 ms |
24808 KB |
Output is correct |
| 79 |
Correct |
677 ms |
24808 KB |
Output is correct |
| 80 |
Correct |
745 ms |
24808 KB |
Output is correct |
| 81 |
Correct |
996 ms |
24808 KB |
Output is correct |
| 82 |
Correct |
1971 ms |
42796 KB |
Output is correct |
| 83 |
Correct |
874 ms |
63392 KB |
Output is correct |
| 84 |
Runtime error |
1506 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. |
| 85 |
Halted |
0 ms |
0 KB |
- |
