/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")
//*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int ,int > pii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll maxn = 2e6+100;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);
#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}
int l , q;
int a[maxn];
string s;
int ans[maxn];
int p[30];
void sub1(){
for(int i = 0 ; i < p[l] ; i ++){
int res = 0;
int x = i;
for(int j = l ; j >= 0 ; j --){
if(x >= 2*p[j]){
x = i;
x-=2*p[j];
ans[i] = ans[x] + ans[x + p[j]];
break;
}
if(x >= p[j])
res += (1 << j);
x%=p[j];
if(j == 0)ans[i] = a[res];
}
}
while(q -- ){
string t;
cin >> t;
reverse(t.begin() , t.end());
int x = 0;
for(int i = 0 ; i < l ; i ++)
if(t[i] == '?')x+=p[i]*2;
else if(t[i] == '1')x+=p[i];
cout << ans[x] << endl;
}
exit(0);
}
string t[maxn];
int32_t main(){
migmig;
cin >> l >> q;
cin >> s;
for(int i = 0 ; i < (1 << l) ; i ++)
a[i] = s[i] - '0';
p[0] = 1;
for(int i = 1 ; i < 16; i ++)
p[i] = p[i - 1] * 3;
if(l <= 15)
sub1();
return(0);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
63212 KB |
Output is correct |
2 |
Correct |
43 ms |
63212 KB |
Output is correct |
3 |
Correct |
49 ms |
63212 KB |
Output is correct |
4 |
Correct |
42 ms |
63212 KB |
Output is correct |
5 |
Correct |
42 ms |
63212 KB |
Output is correct |
6 |
Correct |
42 ms |
63212 KB |
Output is correct |
7 |
Correct |
42 ms |
63212 KB |
Output is correct |
8 |
Correct |
42 ms |
63212 KB |
Output is correct |
9 |
Correct |
41 ms |
63212 KB |
Output is correct |
10 |
Correct |
41 ms |
63212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
63212 KB |
Output is correct |
2 |
Correct |
43 ms |
63212 KB |
Output is correct |
3 |
Correct |
49 ms |
63212 KB |
Output is correct |
4 |
Correct |
42 ms |
63212 KB |
Output is correct |
5 |
Correct |
42 ms |
63212 KB |
Output is correct |
6 |
Correct |
42 ms |
63212 KB |
Output is correct |
7 |
Correct |
42 ms |
63212 KB |
Output is correct |
8 |
Correct |
42 ms |
63212 KB |
Output is correct |
9 |
Correct |
41 ms |
63212 KB |
Output is correct |
10 |
Correct |
41 ms |
63212 KB |
Output is correct |
11 |
Correct |
279 ms |
65536 KB |
Output is correct |
12 |
Correct |
292 ms |
65536 KB |
Output is correct |
13 |
Correct |
310 ms |
65536 KB |
Output is correct |
14 |
Correct |
305 ms |
65536 KB |
Output is correct |
15 |
Correct |
298 ms |
65536 KB |
Output is correct |
16 |
Correct |
305 ms |
65536 KB |
Output is correct |
17 |
Correct |
332 ms |
65536 KB |
Output is correct |
18 |
Correct |
242 ms |
65536 KB |
Output is correct |
19 |
Correct |
269 ms |
65260 KB |
Output is correct |
20 |
Correct |
288 ms |
65536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
63212 KB |
Output is correct |
2 |
Correct |
43 ms |
63212 KB |
Output is correct |
3 |
Correct |
49 ms |
63212 KB |
Output is correct |
4 |
Correct |
42 ms |
63212 KB |
Output is correct |
5 |
Correct |
42 ms |
63212 KB |
Output is correct |
6 |
Correct |
42 ms |
63212 KB |
Output is correct |
7 |
Correct |
42 ms |
63212 KB |
Output is correct |
8 |
Correct |
42 ms |
63212 KB |
Output is correct |
9 |
Correct |
41 ms |
63212 KB |
Output is correct |
10 |
Correct |
41 ms |
63212 KB |
Output is correct |
11 |
Correct |
279 ms |
65536 KB |
Output is correct |
12 |
Correct |
292 ms |
65536 KB |
Output is correct |
13 |
Correct |
310 ms |
65536 KB |
Output is correct |
14 |
Correct |
305 ms |
65536 KB |
Output is correct |
15 |
Correct |
298 ms |
65536 KB |
Output is correct |
16 |
Correct |
305 ms |
65536 KB |
Output is correct |
17 |
Correct |
332 ms |
65536 KB |
Output is correct |
18 |
Correct |
242 ms |
65536 KB |
Output is correct |
19 |
Correct |
269 ms |
65260 KB |
Output is correct |
20 |
Correct |
288 ms |
65536 KB |
Output is correct |
21 |
Runtime error |
60 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
63212 KB |
Output is correct |
2 |
Correct |
43 ms |
63212 KB |
Output is correct |
3 |
Correct |
49 ms |
63212 KB |
Output is correct |
4 |
Correct |
42 ms |
63212 KB |
Output is correct |
5 |
Correct |
42 ms |
63212 KB |
Output is correct |
6 |
Correct |
42 ms |
63212 KB |
Output is correct |
7 |
Correct |
42 ms |
63212 KB |
Output is correct |
8 |
Correct |
42 ms |
63212 KB |
Output is correct |
9 |
Correct |
41 ms |
63212 KB |
Output is correct |
10 |
Correct |
41 ms |
63212 KB |
Output is correct |
11 |
Runtime error |
47 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
63212 KB |
Output is correct |
2 |
Correct |
43 ms |
63212 KB |
Output is correct |
3 |
Correct |
49 ms |
63212 KB |
Output is correct |
4 |
Correct |
42 ms |
63212 KB |
Output is correct |
5 |
Correct |
42 ms |
63212 KB |
Output is correct |
6 |
Correct |
42 ms |
63212 KB |
Output is correct |
7 |
Correct |
42 ms |
63212 KB |
Output is correct |
8 |
Correct |
42 ms |
63212 KB |
Output is correct |
9 |
Correct |
41 ms |
63212 KB |
Output is correct |
10 |
Correct |
41 ms |
63212 KB |
Output is correct |
11 |
Correct |
279 ms |
65536 KB |
Output is correct |
12 |
Correct |
292 ms |
65536 KB |
Output is correct |
13 |
Correct |
310 ms |
65536 KB |
Output is correct |
14 |
Correct |
305 ms |
65536 KB |
Output is correct |
15 |
Correct |
298 ms |
65536 KB |
Output is correct |
16 |
Correct |
305 ms |
65536 KB |
Output is correct |
17 |
Correct |
332 ms |
65536 KB |
Output is correct |
18 |
Correct |
242 ms |
65536 KB |
Output is correct |
19 |
Correct |
269 ms |
65260 KB |
Output is correct |
20 |
Correct |
288 ms |
65536 KB |
Output is correct |
21 |
Runtime error |
60 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
22 |
Halted |
0 ms |
0 KB |
- |