#include<iostream>
using namespace std;
const int MAXN = 21;
int n, q;
char l[MAXN];
int val[1<<MAXN], sum0[1<<MAXN], sum1[1<<MAXN];
void precompute () {
for (int i=0; i<(1<<n); 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)];
}
}
}
void ispis (int x) {
for (int i=n-1; i>=0; i--) {
cout << (bool) (x & (1<<i));
}
cout << endl;
}
int main () {
cin >> n >> q;
for (int i=0; i<(1<<n); i++) {
char c;
cin >> c;
val[i] = c - '0';
}
precompute();
for (int tc=0; tc<q; tc++) {
int a = 0, b = 0, c = 0;
for (int i=0; i<n; i++) {
cin >> l[i];
if (l[i] == '?') {
a ^= (1<<(n-1-i));
} else if (l[i] == '0') {
b ^= (1<<(n-1-i));
} else {
c ^= (1<<(n-1-i));
}
}
int sol = 0, mask = 0;
if (__builtin_popcount(a) <= n/3) {
do {
sol += val[mask | c];
} while (mask = (mask-a) & a);
} else if (__builtin_popcount(b) <= n/3) {
do {
if (__builtin_popcount(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 (__builtin_popcount(mask | a) & 1) {
sol -= sum0[mask | a];
} else {
sol += sum0[mask | a];
}
} while (mask = (mask-c) & c);
if (sol < 0) sol = -sol;
}
printf("%d\n", sol);
}
return 0;
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:55:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} while (mask = (mask-a) & a);
~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:63:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} while (mask = (mask-b) & b);
~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:72:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} while (mask = (mask-c) & c);
~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
5 ms |
452 KB |
Output is correct |
3 |
Correct |
7 ms |
648 KB |
Output is correct |
4 |
Correct |
8 ms |
648 KB |
Output is correct |
5 |
Correct |
5 ms |
648 KB |
Output is correct |
6 |
Correct |
5 ms |
648 KB |
Output is correct |
7 |
Correct |
6 ms |
748 KB |
Output is correct |
8 |
Correct |
5 ms |
748 KB |
Output is correct |
9 |
Correct |
6 ms |
748 KB |
Output is correct |
10 |
Correct |
6 ms |
748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
5 ms |
452 KB |
Output is correct |
3 |
Correct |
7 ms |
648 KB |
Output is correct |
4 |
Correct |
8 ms |
648 KB |
Output is correct |
5 |
Correct |
5 ms |
648 KB |
Output is correct |
6 |
Correct |
5 ms |
648 KB |
Output is correct |
7 |
Correct |
6 ms |
748 KB |
Output is correct |
8 |
Correct |
5 ms |
748 KB |
Output is correct |
9 |
Correct |
6 ms |
748 KB |
Output is correct |
10 |
Correct |
6 ms |
748 KB |
Output is correct |
11 |
Execution timed out |
2019 ms |
11072 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
5 ms |
452 KB |
Output is correct |
3 |
Correct |
7 ms |
648 KB |
Output is correct |
4 |
Correct |
8 ms |
648 KB |
Output is correct |
5 |
Correct |
5 ms |
648 KB |
Output is correct |
6 |
Correct |
5 ms |
648 KB |
Output is correct |
7 |
Correct |
6 ms |
748 KB |
Output is correct |
8 |
Correct |
5 ms |
748 KB |
Output is correct |
9 |
Correct |
6 ms |
748 KB |
Output is correct |
10 |
Correct |
6 ms |
748 KB |
Output is correct |
11 |
Execution timed out |
2019 ms |
11072 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
5 ms |
452 KB |
Output is correct |
3 |
Correct |
7 ms |
648 KB |
Output is correct |
4 |
Correct |
8 ms |
648 KB |
Output is correct |
5 |
Correct |
5 ms |
648 KB |
Output is correct |
6 |
Correct |
5 ms |
648 KB |
Output is correct |
7 |
Correct |
6 ms |
748 KB |
Output is correct |
8 |
Correct |
5 ms |
748 KB |
Output is correct |
9 |
Correct |
6 ms |
748 KB |
Output is correct |
10 |
Correct |
6 ms |
748 KB |
Output is correct |
11 |
Correct |
378 ms |
23024 KB |
Output is correct |
12 |
Correct |
321 ms |
25224 KB |
Output is correct |
13 |
Correct |
293 ms |
27136 KB |
Output is correct |
14 |
Correct |
427 ms |
29120 KB |
Output is correct |
15 |
Correct |
330 ms |
31396 KB |
Output is correct |
16 |
Correct |
364 ms |
33208 KB |
Output is correct |
17 |
Correct |
344 ms |
35376 KB |
Output is correct |
18 |
Correct |
343 ms |
37560 KB |
Output is correct |
19 |
Correct |
316 ms |
39464 KB |
Output is correct |
20 |
Correct |
284 ms |
41808 KB |
Output is correct |
21 |
Correct |
334 ms |
43664 KB |
Output is correct |
22 |
Correct |
380 ms |
45684 KB |
Output is correct |
23 |
Correct |
302 ms |
47624 KB |
Output is correct |
24 |
Correct |
376 ms |
49952 KB |
Output is correct |
25 |
Correct |
388 ms |
51808 KB |
Output is correct |
26 |
Correct |
293 ms |
53936 KB |
Output is correct |
27 |
Correct |
275 ms |
56100 KB |
Output is correct |
28 |
Correct |
314 ms |
58000 KB |
Output is correct |
29 |
Correct |
345 ms |
60108 KB |
Output is correct |
30 |
Correct |
415 ms |
62160 KB |
Output is correct |
31 |
Correct |
297 ms |
64100 KB |
Output is correct |
32 |
Runtime error |
386 ms |
66408 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. |
33 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
5 ms |
452 KB |
Output is correct |
3 |
Correct |
7 ms |
648 KB |
Output is correct |
4 |
Correct |
8 ms |
648 KB |
Output is correct |
5 |
Correct |
5 ms |
648 KB |
Output is correct |
6 |
Correct |
5 ms |
648 KB |
Output is correct |
7 |
Correct |
6 ms |
748 KB |
Output is correct |
8 |
Correct |
5 ms |
748 KB |
Output is correct |
9 |
Correct |
6 ms |
748 KB |
Output is correct |
10 |
Correct |
6 ms |
748 KB |
Output is correct |
11 |
Execution timed out |
2019 ms |
11072 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |