/*
#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);
}
vector < string > t;
int res[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 <= 9)
sub1();
t.reserve(q + 1);
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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
