#include <bits/stdc++.h>
using namespace std;
const int maxn = 13;
int dp[(1<<maxn) + 10][(1<<maxn) + 10], nxt[(1<<maxn) + 10];
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int l, q;
cin >> l >> q;
vector<int> v((1<<l));
for(int i=0; i<(1<<l); i++){
char a;
cin >> a;
v[i] = a - '0';
}
for(int i=1; i<(1<<l); i++) nxt[i] = (i&-i); // rightmost set bit tipo na BIT -> ok
for(int a=(1<<l)-1; a>=0; a--){
dp[a][0] = v[a]; // caso base -> ok
for(int b=1; b<(1<<l); b++){
int x = nxt[b];
dp[a][b] = dp[a|x][b^x] + dp[a][b^x]; // unicos dois casos -> ok
}
}
while(q--){
string s;
cin >> s;
int a = 0, b = 0;
for(int i=0; i<l; i++){
if(s[i] == '1') a += (1<<(l-i-1));
if(s[i] == '?') b += (1<<(l-i-1));
}
cout << dp[a][b] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 4 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 5 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 6 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 7 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 8 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 9 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 10 |
Correct |
7 ms |
8576 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 4 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 5 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 6 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 7 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 8 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 9 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 10 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 11 |
Correct |
240 ms |
12600 KB |
Output is correct |
| 12 |
Correct |
240 ms |
12280 KB |
Output is correct |
| 13 |
Correct |
252 ms |
11512 KB |
Output is correct |
| 14 |
Correct |
252 ms |
11640 KB |
Output is correct |
| 15 |
Correct |
237 ms |
12664 KB |
Output is correct |
| 16 |
Correct |
290 ms |
11760 KB |
Output is correct |
| 17 |
Correct |
290 ms |
11768 KB |
Output is correct |
| 18 |
Correct |
195 ms |
13668 KB |
Output is correct |
| 19 |
Correct |
235 ms |
10624 KB |
Output is correct |
| 20 |
Correct |
244 ms |
12280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 4 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 5 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 6 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 7 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 8 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 9 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 10 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 11 |
Correct |
240 ms |
12600 KB |
Output is correct |
| 12 |
Correct |
240 ms |
12280 KB |
Output is correct |
| 13 |
Correct |
252 ms |
11512 KB |
Output is correct |
| 14 |
Correct |
252 ms |
11640 KB |
Output is correct |
| 15 |
Correct |
237 ms |
12664 KB |
Output is correct |
| 16 |
Correct |
290 ms |
11760 KB |
Output is correct |
| 17 |
Correct |
290 ms |
11768 KB |
Output is correct |
| 18 |
Correct |
195 ms |
13668 KB |
Output is correct |
| 19 |
Correct |
235 ms |
10624 KB |
Output is correct |
| 20 |
Correct |
244 ms |
12280 KB |
Output is correct |
| 21 |
Runtime error |
83 ms |
65540 KB |
Execution killed with signal 9 |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 4 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 5 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 6 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 7 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 8 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 9 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 10 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 11 |
Runtime error |
46 ms |
17152 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 2 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 3 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 4 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 5 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 6 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 7 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 8 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 9 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 10 |
Correct |
7 ms |
8576 KB |
Output is correct |
| 11 |
Correct |
240 ms |
12600 KB |
Output is correct |
| 12 |
Correct |
240 ms |
12280 KB |
Output is correct |
| 13 |
Correct |
252 ms |
11512 KB |
Output is correct |
| 14 |
Correct |
252 ms |
11640 KB |
Output is correct |
| 15 |
Correct |
237 ms |
12664 KB |
Output is correct |
| 16 |
Correct |
290 ms |
11760 KB |
Output is correct |
| 17 |
Correct |
290 ms |
11768 KB |
Output is correct |
| 18 |
Correct |
195 ms |
13668 KB |
Output is correct |
| 19 |
Correct |
235 ms |
10624 KB |
Output is correct |
| 20 |
Correct |
244 ms |
12280 KB |
Output is correct |
| 21 |
Runtime error |
83 ms |
65540 KB |
Execution killed with signal 9 |
| 22 |
Halted |
0 ms |
0 KB |
- |
