#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], pc[1<<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)];
}
}
}
void ispis (int x) {
for (int i=n-1; i>=0; i--) {
cout << (bool) (x & (1<<i));
}
cout << endl;
}
int main () {
std::ios::sync_with_stdio(false);
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, cnt = 0;
if (pc[a] <= n/3) {
do {
cnt++;
sol += val[mask | c];
} while (mask = (mask-a) & a);
} else if (pc[b] <= n/3) {
do {
cnt++;
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 {
cnt++;
if (pc[mask | a] & 1) {
sol -= sum0[mask | a];
} else {
sol += sum0[mask | a];
}
} while (mask = (mask-c) & c);
if (sol < 0) sol = -sol;
}
if (cnt > 64) cout << 1/0;
cout << sol << "\n";
}
return 0;
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:58:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} while (mask = (mask-a) & a);
~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:67:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} while (mask = (mask-b) & b);
~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:77:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
} while (mask = (mask-c) & c);
~~~~~^~~~~~~~~~~~~~
snake_escaping.cpp:80:26: warning: division by zero [-Wdiv-by-zero]
if (cnt > 64) cout << 1/0;
~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
484 KB |
Output is correct |
| 3 |
Correct |
4 ms |
560 KB |
Output is correct |
| 4 |
Correct |
4 ms |
560 KB |
Output is correct |
| 5 |
Correct |
4 ms |
580 KB |
Output is correct |
| 6 |
Correct |
4 ms |
688 KB |
Output is correct |
| 7 |
Correct |
6 ms |
688 KB |
Output is correct |
| 8 |
Correct |
6 ms |
704 KB |
Output is correct |
| 9 |
Correct |
5 ms |
704 KB |
Output is correct |
| 10 |
Correct |
5 ms |
704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
484 KB |
Output is correct |
| 3 |
Correct |
4 ms |
560 KB |
Output is correct |
| 4 |
Correct |
4 ms |
560 KB |
Output is correct |
| 5 |
Correct |
4 ms |
580 KB |
Output is correct |
| 6 |
Correct |
4 ms |
688 KB |
Output is correct |
| 7 |
Correct |
6 ms |
688 KB |
Output is correct |
| 8 |
Correct |
6 ms |
704 KB |
Output is correct |
| 9 |
Correct |
5 ms |
704 KB |
Output is correct |
| 10 |
Correct |
5 ms |
704 KB |
Output is correct |
| 11 |
Correct |
1854 ms |
4752 KB |
Output is correct |
| 12 |
Correct |
1763 ms |
4752 KB |
Output is correct |
| 13 |
Correct |
1780 ms |
14388 KB |
Output is correct |
| 14 |
Correct |
1808 ms |
25432 KB |
Output is correct |
| 15 |
Execution timed out |
2048 ms |
37044 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
484 KB |
Output is correct |
| 3 |
Correct |
4 ms |
560 KB |
Output is correct |
| 4 |
Correct |
4 ms |
560 KB |
Output is correct |
| 5 |
Correct |
4 ms |
580 KB |
Output is correct |
| 6 |
Correct |
4 ms |
688 KB |
Output is correct |
| 7 |
Correct |
6 ms |
688 KB |
Output is correct |
| 8 |
Correct |
6 ms |
704 KB |
Output is correct |
| 9 |
Correct |
5 ms |
704 KB |
Output is correct |
| 10 |
Correct |
5 ms |
704 KB |
Output is correct |
| 11 |
Correct |
1854 ms |
4752 KB |
Output is correct |
| 12 |
Correct |
1763 ms |
4752 KB |
Output is correct |
| 13 |
Correct |
1780 ms |
14388 KB |
Output is correct |
| 14 |
Correct |
1808 ms |
25432 KB |
Output is correct |
| 15 |
Execution timed out |
2048 ms |
37044 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
484 KB |
Output is correct |
| 3 |
Correct |
4 ms |
560 KB |
Output is correct |
| 4 |
Correct |
4 ms |
560 KB |
Output is correct |
| 5 |
Correct |
4 ms |
580 KB |
Output is correct |
| 6 |
Correct |
4 ms |
688 KB |
Output is correct |
| 7 |
Correct |
6 ms |
688 KB |
Output is correct |
| 8 |
Correct |
6 ms |
704 KB |
Output is correct |
| 9 |
Correct |
5 ms |
704 KB |
Output is correct |
| 10 |
Correct |
5 ms |
704 KB |
Output is correct |
| 11 |
Correct |
189 ms |
49572 KB |
Output is correct |
| 12 |
Correct |
241 ms |
49584 KB |
Output is correct |
| 13 |
Correct |
211 ms |
49592 KB |
Output is correct |
| 14 |
Correct |
286 ms |
49688 KB |
Output is correct |
| 15 |
Correct |
216 ms |
49728 KB |
Output is correct |
| 16 |
Correct |
304 ms |
49728 KB |
Output is correct |
| 17 |
Correct |
239 ms |
49728 KB |
Output is correct |
| 18 |
Correct |
199 ms |
49924 KB |
Output is correct |
| 19 |
Correct |
191 ms |
49924 KB |
Output is correct |
| 20 |
Correct |
213 ms |
49924 KB |
Output is correct |
| 21 |
Correct |
274 ms |
49924 KB |
Output is correct |
| 22 |
Correct |
290 ms |
49924 KB |
Output is correct |
| 23 |
Correct |
184 ms |
49924 KB |
Output is correct |
| 24 |
Correct |
205 ms |
49924 KB |
Output is correct |
| 25 |
Correct |
243 ms |
49924 KB |
Output is correct |
| 26 |
Correct |
192 ms |
49924 KB |
Output is correct |
| 27 |
Correct |
208 ms |
49924 KB |
Output is correct |
| 28 |
Correct |
198 ms |
49924 KB |
Output is correct |
| 29 |
Correct |
286 ms |
49924 KB |
Output is correct |
| 30 |
Correct |
224 ms |
49924 KB |
Output is correct |
| 31 |
Correct |
173 ms |
49924 KB |
Output is correct |
| 32 |
Correct |
258 ms |
49924 KB |
Output is correct |
| 33 |
Correct |
206 ms |
49924 KB |
Output is correct |
| 34 |
Correct |
195 ms |
49924 KB |
Output is correct |
| 35 |
Correct |
229 ms |
49924 KB |
Output is correct |
| 36 |
Correct |
209 ms |
49924 KB |
Output is correct |
| 37 |
Correct |
275 ms |
49924 KB |
Output is correct |
| 38 |
Correct |
201 ms |
49924 KB |
Output is correct |
| 39 |
Correct |
254 ms |
49924 KB |
Output is correct |
| 40 |
Correct |
233 ms |
49924 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
484 KB |
Output is correct |
| 3 |
Correct |
4 ms |
560 KB |
Output is correct |
| 4 |
Correct |
4 ms |
560 KB |
Output is correct |
| 5 |
Correct |
4 ms |
580 KB |
Output is correct |
| 6 |
Correct |
4 ms |
688 KB |
Output is correct |
| 7 |
Correct |
6 ms |
688 KB |
Output is correct |
| 8 |
Correct |
6 ms |
704 KB |
Output is correct |
| 9 |
Correct |
5 ms |
704 KB |
Output is correct |
| 10 |
Correct |
5 ms |
704 KB |
Output is correct |
| 11 |
Correct |
1854 ms |
4752 KB |
Output is correct |
| 12 |
Correct |
1763 ms |
4752 KB |
Output is correct |
| 13 |
Correct |
1780 ms |
14388 KB |
Output is correct |
| 14 |
Correct |
1808 ms |
25432 KB |
Output is correct |
| 15 |
Execution timed out |
2048 ms |
37044 KB |
Time limit exceeded |
| 16 |
Halted |
0 ms |
0 KB |
- |
