/*
#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 = 1e6+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];
string t[maxn];
int res[maxn];
void sub1(){
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;
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;
}
}
int32_t main(){
migmig;
cin >> l >> q;
if(l <= 15){
sub1();
return(0);
}
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;
for(int i = 1 ; i <= q ; i ++)
cin >> t[i] , reverse(t[i].begin() , t[i].end());
for(int k = 0 ; k < 128 ; k ++){
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 * 128 + k];
}
}
for(int i = 1 ; i <= q ; i ++){
bool ok = 1;
for(int j = 0 ; j < 7 ; j ++){
if(k&(1 << j)){if(t[i][j] == '0'){ok=0 ;break;}}
else if(t[i][j] == '1'){ok=0 ;break;}
}
if(!ok)continue;
int x = 0;
for(int j = 7 ; j < l ; j ++)
if(t[i][j] == '?')x+=p[i]*2;
else if(t[i][j] == '1')x+=p[i];
res[i] += ans[x];
}
}
for(int i = 1; i <= q ; i ++)
cout << res[i] << endl;
return(0);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
31980 KB |
Output is correct |
2 |
Correct |
22 ms |
31980 KB |
Output is correct |
3 |
Correct |
22 ms |
31980 KB |
Output is correct |
4 |
Correct |
22 ms |
31980 KB |
Output is correct |
5 |
Correct |
22 ms |
31980 KB |
Output is correct |
6 |
Correct |
23 ms |
31980 KB |
Output is correct |
7 |
Correct |
22 ms |
31980 KB |
Output is correct |
8 |
Correct |
22 ms |
31980 KB |
Output is correct |
9 |
Correct |
23 ms |
31852 KB |
Output is correct |
10 |
Correct |
23 ms |
31980 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
31980 KB |
Output is correct |
2 |
Correct |
22 ms |
31980 KB |
Output is correct |
3 |
Correct |
22 ms |
31980 KB |
Output is correct |
4 |
Correct |
22 ms |
31980 KB |
Output is correct |
5 |
Correct |
22 ms |
31980 KB |
Output is correct |
6 |
Correct |
23 ms |
31980 KB |
Output is correct |
7 |
Correct |
22 ms |
31980 KB |
Output is correct |
8 |
Correct |
22 ms |
31980 KB |
Output is correct |
9 |
Correct |
23 ms |
31852 KB |
Output is correct |
10 |
Correct |
23 ms |
31980 KB |
Output is correct |
11 |
Correct |
258 ms |
45164 KB |
Output is correct |
12 |
Correct |
293 ms |
45636 KB |
Output is correct |
13 |
Correct |
278 ms |
44652 KB |
Output is correct |
14 |
Correct |
281 ms |
44780 KB |
Output is correct |
15 |
Correct |
287 ms |
45804 KB |
Output is correct |
16 |
Correct |
293 ms |
44724 KB |
Output is correct |
17 |
Correct |
313 ms |
44908 KB |
Output is correct |
18 |
Correct |
222 ms |
47084 KB |
Output is correct |
19 |
Correct |
257 ms |
43500 KB |
Output is correct |
20 |
Correct |
273 ms |
45292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
31980 KB |
Output is correct |
2 |
Correct |
22 ms |
31980 KB |
Output is correct |
3 |
Correct |
22 ms |
31980 KB |
Output is correct |
4 |
Correct |
22 ms |
31980 KB |
Output is correct |
5 |
Correct |
22 ms |
31980 KB |
Output is correct |
6 |
Correct |
23 ms |
31980 KB |
Output is correct |
7 |
Correct |
22 ms |
31980 KB |
Output is correct |
8 |
Correct |
22 ms |
31980 KB |
Output is correct |
9 |
Correct |
23 ms |
31852 KB |
Output is correct |
10 |
Correct |
23 ms |
31980 KB |
Output is correct |
11 |
Correct |
258 ms |
45164 KB |
Output is correct |
12 |
Correct |
293 ms |
45636 KB |
Output is correct |
13 |
Correct |
278 ms |
44652 KB |
Output is correct |
14 |
Correct |
281 ms |
44780 KB |
Output is correct |
15 |
Correct |
287 ms |
45804 KB |
Output is correct |
16 |
Correct |
293 ms |
44724 KB |
Output is correct |
17 |
Correct |
313 ms |
44908 KB |
Output is correct |
18 |
Correct |
222 ms |
47084 KB |
Output is correct |
19 |
Correct |
257 ms |
43500 KB |
Output is correct |
20 |
Correct |
273 ms |
45292 KB |
Output is correct |
21 |
Runtime error |
369 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
31980 KB |
Output is correct |
2 |
Correct |
22 ms |
31980 KB |
Output is correct |
3 |
Correct |
22 ms |
31980 KB |
Output is correct |
4 |
Correct |
22 ms |
31980 KB |
Output is correct |
5 |
Correct |
22 ms |
31980 KB |
Output is correct |
6 |
Correct |
23 ms |
31980 KB |
Output is correct |
7 |
Correct |
22 ms |
31980 KB |
Output is correct |
8 |
Correct |
22 ms |
31980 KB |
Output is correct |
9 |
Correct |
23 ms |
31852 KB |
Output is correct |
10 |
Correct |
23 ms |
31980 KB |
Output is correct |
11 |
Runtime error |
76 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
31980 KB |
Output is correct |
2 |
Correct |
22 ms |
31980 KB |
Output is correct |
3 |
Correct |
22 ms |
31980 KB |
Output is correct |
4 |
Correct |
22 ms |
31980 KB |
Output is correct |
5 |
Correct |
22 ms |
31980 KB |
Output is correct |
6 |
Correct |
23 ms |
31980 KB |
Output is correct |
7 |
Correct |
22 ms |
31980 KB |
Output is correct |
8 |
Correct |
22 ms |
31980 KB |
Output is correct |
9 |
Correct |
23 ms |
31852 KB |
Output is correct |
10 |
Correct |
23 ms |
31980 KB |
Output is correct |
11 |
Correct |
258 ms |
45164 KB |
Output is correct |
12 |
Correct |
293 ms |
45636 KB |
Output is correct |
13 |
Correct |
278 ms |
44652 KB |
Output is correct |
14 |
Correct |
281 ms |
44780 KB |
Output is correct |
15 |
Correct |
287 ms |
45804 KB |
Output is correct |
16 |
Correct |
293 ms |
44724 KB |
Output is correct |
17 |
Correct |
313 ms |
44908 KB |
Output is correct |
18 |
Correct |
222 ms |
47084 KB |
Output is correct |
19 |
Correct |
257 ms |
43500 KB |
Output is correct |
20 |
Correct |
273 ms |
45292 KB |
Output is correct |
21 |
Runtime error |
369 ms |
65536 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
22 |
Halted |
0 ms |
0 KB |
- |