#include <bits/stdc++.h>
using namespace std;
inline int in() {
int result = 0;
char ch = getchar_unlocked();
while(true) {
if(ch >= '0' && ch <= '9')
break;
ch = getchar_unlocked();
}
result = ch-'0';
while(true) {
ch = getchar_unlocked();
if (ch < '0' || ch > '9')
break;
result = result*10 + (ch - '0');
}
return result;
}
inline void out(int x) {
if(!x) {
putchar_unlocked('0');
return;
}
int rev=x, c=0;
while(!(rev%10)) {
++c;
rev/=10;
}
rev=0;
while(x) {
rev=rev*10+x%10;
x/=10;
}
while(rev) {
putchar_unlocked(rev%10+'0');
rev/=10;
}
while(c--)
putchar_unlocked('0');
}
const int mxL=20, mxQ=1e6;
int l, q, dp[2][1<<mxL];
char s[1<<mxL];
int main() {
l=in(), q=in();
for(int i=0; i<1<<l; ++i)
while(s[i]<'0'||s[i]>'9')
s[i]=getchar_unlocked();
for(int j=0; j<2; ++j) {
for(int i=0; i<1<<l; ++i)
dp[j][i]=s[i]-'0';
for(int k=0; k<l; ++k)
for(int i=0; i<1<<l; ++i)
if(i>>k&1^j)
dp[j][i]+=dp[j][i^1<<k];
}
while(q--) {
int na=0, nb=0, nc=0, ma=0, mb=0, mc=0, ans=0;
for(int i=0; i<l; ++i) {
char c=getchar_unlocked();
if(c=='0') {
++na;
ma|=1<<(l-1-i);
} else if(c=='1') {
++nb;
mb|=1<<(l-1-i);
} else if(c=='?') {
++nc;
mc|=1<<(l-1-i);
} else
--i;
}
if(na<nc||nb<nc) {
bool sw=0;
if(nb>na) {
swap(mb, ma);
sw=1;
}
for(int i=mb; ; i=(i-1)&mb) {
ans+=dp[sw][(sw?(1<<l)-1:0)^i^mb^mc]*(__builtin_popcount(i)&1?-1:1);
if(!i)
break;
}
} else {
for(int i=mc; ; i=(i-1)&mc) {
ans+=s[i|mb]-'0';
if(!i)
break;
}
}
out(ans);
putchar_unlocked('\n');
}
}
Compilation message
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:58:12: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
if(i>>k&1^j)
~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
516 KB |
Output is correct |
| 6 |
Correct |
2 ms |
532 KB |
Output is correct |
| 7 |
Correct |
3 ms |
540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
516 KB |
Output is correct |
| 6 |
Correct |
2 ms |
532 KB |
Output is correct |
| 7 |
Correct |
3 ms |
540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
652 KB |
Output is correct |
| 11 |
Correct |
163 ms |
7228 KB |
Output is correct |
| 12 |
Correct |
171 ms |
7228 KB |
Output is correct |
| 13 |
Correct |
162 ms |
7228 KB |
Output is correct |
| 14 |
Correct |
167 ms |
7228 KB |
Output is correct |
| 15 |
Correct |
158 ms |
8064 KB |
Output is correct |
| 16 |
Correct |
173 ms |
8064 KB |
Output is correct |
| 17 |
Correct |
203 ms |
9004 KB |
Output is correct |
| 18 |
Correct |
103 ms |
11684 KB |
Output is correct |
| 19 |
Correct |
111 ms |
11684 KB |
Output is correct |
| 20 |
Correct |
176 ms |
11684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
516 KB |
Output is correct |
| 6 |
Correct |
2 ms |
532 KB |
Output is correct |
| 7 |
Correct |
3 ms |
540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
652 KB |
Output is correct |
| 11 |
Correct |
163 ms |
7228 KB |
Output is correct |
| 12 |
Correct |
171 ms |
7228 KB |
Output is correct |
| 13 |
Correct |
162 ms |
7228 KB |
Output is correct |
| 14 |
Correct |
167 ms |
7228 KB |
Output is correct |
| 15 |
Correct |
158 ms |
8064 KB |
Output is correct |
| 16 |
Correct |
173 ms |
8064 KB |
Output is correct |
| 17 |
Correct |
203 ms |
9004 KB |
Output is correct |
| 18 |
Correct |
103 ms |
11684 KB |
Output is correct |
| 19 |
Correct |
111 ms |
11684 KB |
Output is correct |
| 20 |
Correct |
176 ms |
11684 KB |
Output is correct |
| 21 |
Correct |
180 ms |
11684 KB |
Output is correct |
| 22 |
Correct |
195 ms |
11684 KB |
Output is correct |
| 23 |
Correct |
237 ms |
11684 KB |
Output is correct |
| 24 |
Correct |
248 ms |
11684 KB |
Output is correct |
| 25 |
Correct |
192 ms |
12228 KB |
Output is correct |
| 26 |
Correct |
264 ms |
12228 KB |
Output is correct |
| 27 |
Correct |
270 ms |
12228 KB |
Output is correct |
| 28 |
Correct |
116 ms |
14700 KB |
Output is correct |
| 29 |
Correct |
168 ms |
14700 KB |
Output is correct |
| 30 |
Correct |
215 ms |
14700 KB |
Output is correct |
| 31 |
Correct |
275 ms |
14700 KB |
Output is correct |
| 32 |
Correct |
309 ms |
14700 KB |
Output is correct |
| 33 |
Correct |
199 ms |
14700 KB |
Output is correct |
| 34 |
Correct |
266 ms |
14700 KB |
Output is correct |
| 35 |
Correct |
293 ms |
14700 KB |
Output is correct |
| 36 |
Correct |
84 ms |
14700 KB |
Output is correct |
| 37 |
Correct |
193 ms |
14700 KB |
Output is correct |
| 38 |
Correct |
159 ms |
14700 KB |
Output is correct |
| 39 |
Correct |
217 ms |
14700 KB |
Output is correct |
| 40 |
Correct |
226 ms |
14700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
516 KB |
Output is correct |
| 6 |
Correct |
2 ms |
532 KB |
Output is correct |
| 7 |
Correct |
3 ms |
540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
652 KB |
Output is correct |
| 11 |
Correct |
112 ms |
19980 KB |
Output is correct |
| 12 |
Correct |
109 ms |
19980 KB |
Output is correct |
| 13 |
Correct |
118 ms |
19980 KB |
Output is correct |
| 14 |
Correct |
152 ms |
19980 KB |
Output is correct |
| 15 |
Correct |
110 ms |
20016 KB |
Output is correct |
| 16 |
Correct |
140 ms |
20016 KB |
Output is correct |
| 17 |
Correct |
124 ms |
20016 KB |
Output is correct |
| 18 |
Correct |
91 ms |
20144 KB |
Output is correct |
| 19 |
Correct |
92 ms |
20144 KB |
Output is correct |
| 20 |
Correct |
109 ms |
20144 KB |
Output is correct |
| 21 |
Correct |
142 ms |
20144 KB |
Output is correct |
| 22 |
Correct |
186 ms |
20144 KB |
Output is correct |
| 23 |
Correct |
110 ms |
20144 KB |
Output is correct |
| 24 |
Correct |
129 ms |
20144 KB |
Output is correct |
| 25 |
Correct |
133 ms |
20144 KB |
Output is correct |
| 26 |
Correct |
107 ms |
20144 KB |
Output is correct |
| 27 |
Correct |
141 ms |
20392 KB |
Output is correct |
| 28 |
Correct |
104 ms |
20392 KB |
Output is correct |
| 29 |
Correct |
117 ms |
20392 KB |
Output is correct |
| 30 |
Correct |
115 ms |
20392 KB |
Output is correct |
| 31 |
Correct |
122 ms |
20392 KB |
Output is correct |
| 32 |
Correct |
163 ms |
20408 KB |
Output is correct |
| 33 |
Correct |
137 ms |
20408 KB |
Output is correct |
| 34 |
Correct |
85 ms |
20408 KB |
Output is correct |
| 35 |
Correct |
136 ms |
20408 KB |
Output is correct |
| 36 |
Correct |
124 ms |
20408 KB |
Output is correct |
| 37 |
Correct |
122 ms |
20408 KB |
Output is correct |
| 38 |
Correct |
130 ms |
20440 KB |
Output is correct |
| 39 |
Correct |
120 ms |
20440 KB |
Output is correct |
| 40 |
Correct |
119 ms |
20440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
456 KB |
Output is correct |
| 4 |
Correct |
3 ms |
468 KB |
Output is correct |
| 5 |
Correct |
2 ms |
516 KB |
Output is correct |
| 6 |
Correct |
2 ms |
532 KB |
Output is correct |
| 7 |
Correct |
3 ms |
540 KB |
Output is correct |
| 8 |
Correct |
2 ms |
628 KB |
Output is correct |
| 9 |
Correct |
3 ms |
640 KB |
Output is correct |
| 10 |
Correct |
3 ms |
652 KB |
Output is correct |
| 11 |
Correct |
163 ms |
7228 KB |
Output is correct |
| 12 |
Correct |
171 ms |
7228 KB |
Output is correct |
| 13 |
Correct |
162 ms |
7228 KB |
Output is correct |
| 14 |
Correct |
167 ms |
7228 KB |
Output is correct |
| 15 |
Correct |
158 ms |
8064 KB |
Output is correct |
| 16 |
Correct |
173 ms |
8064 KB |
Output is correct |
| 17 |
Correct |
203 ms |
9004 KB |
Output is correct |
| 18 |
Correct |
103 ms |
11684 KB |
Output is correct |
| 19 |
Correct |
111 ms |
11684 KB |
Output is correct |
| 20 |
Correct |
176 ms |
11684 KB |
Output is correct |
| 21 |
Correct |
180 ms |
11684 KB |
Output is correct |
| 22 |
Correct |
195 ms |
11684 KB |
Output is correct |
| 23 |
Correct |
237 ms |
11684 KB |
Output is correct |
| 24 |
Correct |
248 ms |
11684 KB |
Output is correct |
| 25 |
Correct |
192 ms |
12228 KB |
Output is correct |
| 26 |
Correct |
264 ms |
12228 KB |
Output is correct |
| 27 |
Correct |
270 ms |
12228 KB |
Output is correct |
| 28 |
Correct |
116 ms |
14700 KB |
Output is correct |
| 29 |
Correct |
168 ms |
14700 KB |
Output is correct |
| 30 |
Correct |
215 ms |
14700 KB |
Output is correct |
| 31 |
Correct |
275 ms |
14700 KB |
Output is correct |
| 32 |
Correct |
309 ms |
14700 KB |
Output is correct |
| 33 |
Correct |
199 ms |
14700 KB |
Output is correct |
| 34 |
Correct |
266 ms |
14700 KB |
Output is correct |
| 35 |
Correct |
293 ms |
14700 KB |
Output is correct |
| 36 |
Correct |
84 ms |
14700 KB |
Output is correct |
| 37 |
Correct |
193 ms |
14700 KB |
Output is correct |
| 38 |
Correct |
159 ms |
14700 KB |
Output is correct |
| 39 |
Correct |
217 ms |
14700 KB |
Output is correct |
| 40 |
Correct |
226 ms |
14700 KB |
Output is correct |
| 41 |
Correct |
112 ms |
19980 KB |
Output is correct |
| 42 |
Correct |
109 ms |
19980 KB |
Output is correct |
| 43 |
Correct |
118 ms |
19980 KB |
Output is correct |
| 44 |
Correct |
152 ms |
19980 KB |
Output is correct |
| 45 |
Correct |
110 ms |
20016 KB |
Output is correct |
| 46 |
Correct |
140 ms |
20016 KB |
Output is correct |
| 47 |
Correct |
124 ms |
20016 KB |
Output is correct |
| 48 |
Correct |
91 ms |
20144 KB |
Output is correct |
| 49 |
Correct |
92 ms |
20144 KB |
Output is correct |
| 50 |
Correct |
109 ms |
20144 KB |
Output is correct |
| 51 |
Correct |
142 ms |
20144 KB |
Output is correct |
| 52 |
Correct |
186 ms |
20144 KB |
Output is correct |
| 53 |
Correct |
110 ms |
20144 KB |
Output is correct |
| 54 |
Correct |
129 ms |
20144 KB |
Output is correct |
| 55 |
Correct |
133 ms |
20144 KB |
Output is correct |
| 56 |
Correct |
107 ms |
20144 KB |
Output is correct |
| 57 |
Correct |
141 ms |
20392 KB |
Output is correct |
| 58 |
Correct |
104 ms |
20392 KB |
Output is correct |
| 59 |
Correct |
117 ms |
20392 KB |
Output is correct |
| 60 |
Correct |
115 ms |
20392 KB |
Output is correct |
| 61 |
Correct |
122 ms |
20392 KB |
Output is correct |
| 62 |
Correct |
163 ms |
20408 KB |
Output is correct |
| 63 |
Correct |
137 ms |
20408 KB |
Output is correct |
| 64 |
Correct |
85 ms |
20408 KB |
Output is correct |
| 65 |
Correct |
136 ms |
20408 KB |
Output is correct |
| 66 |
Correct |
124 ms |
20408 KB |
Output is correct |
| 67 |
Correct |
122 ms |
20408 KB |
Output is correct |
| 68 |
Correct |
130 ms |
20440 KB |
Output is correct |
| 69 |
Correct |
120 ms |
20440 KB |
Output is correct |
| 70 |
Correct |
119 ms |
20440 KB |
Output is correct |
| 71 |
Correct |
466 ms |
25116 KB |
Output is correct |
| 72 |
Correct |
490 ms |
27856 KB |
Output is correct |
| 73 |
Correct |
682 ms |
27856 KB |
Output is correct |
| 74 |
Correct |
1235 ms |
27856 KB |
Output is correct |
| 75 |
Correct |
467 ms |
28776 KB |
Output is correct |
| 76 |
Correct |
1507 ms |
28776 KB |
Output is correct |
| 77 |
Correct |
1039 ms |
28776 KB |
Output is correct |
| 78 |
Correct |
305 ms |
31360 KB |
Output is correct |
| 79 |
Correct |
456 ms |
31360 KB |
Output is correct |
| 80 |
Correct |
502 ms |
31360 KB |
Output is correct |
| 81 |
Correct |
843 ms |
31360 KB |
Output is correct |
| 82 |
Correct |
1883 ms |
49196 KB |
Output is correct |
| 83 |
Correct |
442 ms |
49196 KB |
Output is correct |
| 84 |
Runtime error |
882 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 |
- |
