#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 2e6 + 5, mod = 1e9 + 7; // !
int t,dp1[N][22],dp2[N][22],L,q;
vector<int> cnt[4];
main(){
cin >> L >> q;
string s;
cin >> s;
for(int i = 0; i < (1 << L); i++) {
dp1[i][0] = s[i] - '0';
for(int j = 0; j < L; j++) {
if(j) dp1[i][j] = dp1[i][j - 1];
if((1 << j) & i) dp1[i][j] += dp1[i ^ (1 << j)][j];
}
}
for(int i = (1 << L) - 1; i >= 0; i--) {
dp2[i][0] = s[i] - '0';
for(int j = 0; j < L; j++) {
if(j) dp2[i][j] = dp2[i][j - 1];
if(!((1 << j) & i)) dp2[i][j] += dp2[i ^ (1 << j)][j];
}
}
while(q--) {
string t;
cin >> t;
int x = 0;
reverse(t.begin(),t.end());
int c = 0, a = 0, b = 0;
for(int i = 0; i < 3; i++) cnt[i].clear();
for(int i = 0; i < t.size(); i++) {
if(t[i] == '0') cnt[0].push_back(i), a += 1 << i;
else if(t[i] == '1') cnt[1].push_back(i),b += 1 << i;
else cnt[2].push_back(i),c += 1 << i;
}
int ans = 0;
if(cnt[2].size() < 7) {
for(int i = c;; i = (i - 1) & c) {
ans += s[i | b] - '0';
if(!i) break;
}
}
else if(cnt[1].size() < 7) {
int p = __builtin_popcount(b) % 2;
for(int i = b;; i = (i - 1) & b) {
ans += (__builtin_popcount(i) % 2 == p ? 1 : -1)
* dp1[i | c][L - 1];
if(!i) break;
}
}
else {
for(int i = a;; i = (i - 1) & a) {
ans += (__builtin_popcount(i) % 2 == 0 ? 1 : -1)
* dp2[i | b][L - 1];
if(!i) break;
}
}
cout << ans << endl;
}
}
Compilation message
snake_escaping.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
10 | main(){
| ^~~~
snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:35:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0; i < t.size(); i++) {
| ~~^~~~~~~~~~
snake_escaping.cpp:31:29: warning: unused variable 'x' [-Wunused-variable]
31 | int x = 0;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
588 KB |
Output is correct |
| 2 |
Correct |
3 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
588 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
3 ms |
588 KB |
Output is correct |
| 6 |
Correct |
3 ms |
588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
588 KB |
Output is correct |
| 2 |
Correct |
3 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
588 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
3 ms |
588 KB |
Output is correct |
| 6 |
Correct |
3 ms |
588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| 11 |
Correct |
1891 ms |
15396 KB |
Output is correct |
| 12 |
Execution timed out |
2008 ms |
15040 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
588 KB |
Output is correct |
| 2 |
Correct |
3 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
588 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
3 ms |
588 KB |
Output is correct |
| 6 |
Correct |
3 ms |
588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| 11 |
Correct |
1891 ms |
15396 KB |
Output is correct |
| 12 |
Execution timed out |
2008 ms |
15040 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
588 KB |
Output is correct |
| 2 |
Correct |
3 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
588 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
3 ms |
588 KB |
Output is correct |
| 6 |
Correct |
3 ms |
588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| 11 |
Runtime error |
101 ms |
65540 KB |
Execution killed with signal 9 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
588 KB |
Output is correct |
| 2 |
Correct |
3 ms |
588 KB |
Output is correct |
| 3 |
Correct |
3 ms |
588 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| 5 |
Correct |
3 ms |
588 KB |
Output is correct |
| 6 |
Correct |
3 ms |
588 KB |
Output is correct |
| 7 |
Correct |
3 ms |
588 KB |
Output is correct |
| 8 |
Correct |
2 ms |
588 KB |
Output is correct |
| 9 |
Correct |
3 ms |
564 KB |
Output is correct |
| 10 |
Correct |
3 ms |
588 KB |
Output is correct |
| 11 |
Correct |
1891 ms |
15396 KB |
Output is correct |
| 12 |
Execution timed out |
2008 ms |
15040 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
