#include "bits/stdc++.h"
using namespace std;
int l,q,n;
int pw[25];
bool comp(int a, int b){
vector<int> x,y;
int cntx=0,cnty=0;
for(int j=0; j<l; j++){
int cr = a%3; a/=3;
if(cr==2) cntx++;
}
for(int j=0; j<l; j++){
int cr = b%3; b/=3;
if(cr==2) cnty++;
}
return cntx<cnty;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin>>l>>q; n=1<<l;
string s; cin>>s;
int tox[n];
for(int i=0; i<n; i++) tox[i] = s[i]-'0';
pw[0]=1;
int k=1; for(int i=1; i<=l; i++){ k*=3; pw[i]=k;}
int ans[k]; memset(ans,0,sizeof(ans));
int ord[k];
for(int i=0; i<k; i++) ord[i]=i;
sort(ord,ord+k,comp);
for(int i=0; i<n; i++){
int v = ord[i], vk=v;
int tot = 0;
for(int j=0; j<l; j++){
int cr = v%3; v/=3;
tot += ((1<<j)*cr);
}
ans[vk] = tox[tot];
}
for(int ahc=n; ahc<k; ahc++){
int v = ord[ahc], tk = ord[ahc], tt = ord[ahc], vk = ord[ahc];
for(int i=0; i<l; i++){
int cr = v%3; v/=3;
if(cr==2){
tk-=(2*pw[i]);
tt-=(1*pw[i]);
break;
}
}
ans[vk] = ans[tk]+ans[tt];
}
/*for(int ahc=0; ahc<k; ahc++){
vector<int> v; int cr=ahc;
for(int j=0; j<l; j++){
v.push_back(cr%3); cr/=3;
}
for(int i=0; i<n; i++){
bitset<13> b(i); bool f=1;
for(int j=0; j<l; j++){
if(v[j]!=2 && (b[j]!=v[j])){ f=0; break;}
}
if(f) ans[ahc] += tox[i];
}
}*/
for(int ahc=0; ahc<q; ahc++){
string s; cin>>s;
int qr=0;
for(int i=0; i<l; i++){
int pwer = l-i-1;
if(s[i]=='1') qr += (pw[pwer]);
if(s[i]=='?') qr += (2*pw[pwer]);
}
cout<<ans[qr]<<"\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
748 KB |
Output is correct |
2 |
Correct |
44 ms |
748 KB |
Output is correct |
3 |
Correct |
47 ms |
748 KB |
Output is correct |
4 |
Correct |
46 ms |
748 KB |
Output is correct |
5 |
Correct |
43 ms |
748 KB |
Output is correct |
6 |
Correct |
43 ms |
748 KB |
Output is correct |
7 |
Correct |
45 ms |
852 KB |
Output is correct |
8 |
Correct |
50 ms |
748 KB |
Output is correct |
9 |
Correct |
43 ms |
768 KB |
Output is correct |
10 |
Correct |
43 ms |
748 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
748 KB |
Output is correct |
2 |
Correct |
44 ms |
748 KB |
Output is correct |
3 |
Correct |
47 ms |
748 KB |
Output is correct |
4 |
Correct |
46 ms |
748 KB |
Output is correct |
5 |
Correct |
43 ms |
748 KB |
Output is correct |
6 |
Correct |
43 ms |
748 KB |
Output is correct |
7 |
Correct |
45 ms |
852 KB |
Output is correct |
8 |
Correct |
50 ms |
748 KB |
Output is correct |
9 |
Correct |
43 ms |
768 KB |
Output is correct |
10 |
Correct |
43 ms |
748 KB |
Output is correct |
11 |
Correct |
283 ms |
4844 KB |
Output is correct |
12 |
Correct |
302 ms |
4460 KB |
Output is correct |
13 |
Correct |
300 ms |
3820 KB |
Output is correct |
14 |
Correct |
305 ms |
3820 KB |
Output is correct |
15 |
Correct |
319 ms |
4996 KB |
Output is correct |
16 |
Correct |
311 ms |
3948 KB |
Output is correct |
17 |
Correct |
323 ms |
3948 KB |
Output is correct |
18 |
Correct |
249 ms |
5996 KB |
Output is correct |
19 |
Correct |
282 ms |
2796 KB |
Output is correct |
20 |
Correct |
293 ms |
4460 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
748 KB |
Output is correct |
2 |
Correct |
44 ms |
748 KB |
Output is correct |
3 |
Correct |
47 ms |
748 KB |
Output is correct |
4 |
Correct |
46 ms |
748 KB |
Output is correct |
5 |
Correct |
43 ms |
748 KB |
Output is correct |
6 |
Correct |
43 ms |
748 KB |
Output is correct |
7 |
Correct |
45 ms |
852 KB |
Output is correct |
8 |
Correct |
50 ms |
748 KB |
Output is correct |
9 |
Correct |
43 ms |
768 KB |
Output is correct |
10 |
Correct |
43 ms |
748 KB |
Output is correct |
11 |
Correct |
283 ms |
4844 KB |
Output is correct |
12 |
Correct |
302 ms |
4460 KB |
Output is correct |
13 |
Correct |
300 ms |
3820 KB |
Output is correct |
14 |
Correct |
305 ms |
3820 KB |
Output is correct |
15 |
Correct |
319 ms |
4996 KB |
Output is correct |
16 |
Correct |
311 ms |
3948 KB |
Output is correct |
17 |
Correct |
323 ms |
3948 KB |
Output is correct |
18 |
Correct |
249 ms |
5996 KB |
Output is correct |
19 |
Correct |
282 ms |
2796 KB |
Output is correct |
20 |
Correct |
293 ms |
4460 KB |
Output is correct |
21 |
Execution timed out |
2082 ms |
14572 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
748 KB |
Output is correct |
2 |
Correct |
44 ms |
748 KB |
Output is correct |
3 |
Correct |
47 ms |
748 KB |
Output is correct |
4 |
Correct |
46 ms |
748 KB |
Output is correct |
5 |
Correct |
43 ms |
748 KB |
Output is correct |
6 |
Correct |
43 ms |
748 KB |
Output is correct |
7 |
Correct |
45 ms |
852 KB |
Output is correct |
8 |
Correct |
50 ms |
748 KB |
Output is correct |
9 |
Correct |
43 ms |
768 KB |
Output is correct |
10 |
Correct |
43 ms |
748 KB |
Output is correct |
11 |
Runtime error |
15 ms |
11152 KB |
Execution killed with signal 7 |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
748 KB |
Output is correct |
2 |
Correct |
44 ms |
748 KB |
Output is correct |
3 |
Correct |
47 ms |
748 KB |
Output is correct |
4 |
Correct |
46 ms |
748 KB |
Output is correct |
5 |
Correct |
43 ms |
748 KB |
Output is correct |
6 |
Correct |
43 ms |
748 KB |
Output is correct |
7 |
Correct |
45 ms |
852 KB |
Output is correct |
8 |
Correct |
50 ms |
748 KB |
Output is correct |
9 |
Correct |
43 ms |
768 KB |
Output is correct |
10 |
Correct |
43 ms |
748 KB |
Output is correct |
11 |
Correct |
283 ms |
4844 KB |
Output is correct |
12 |
Correct |
302 ms |
4460 KB |
Output is correct |
13 |
Correct |
300 ms |
3820 KB |
Output is correct |
14 |
Correct |
305 ms |
3820 KB |
Output is correct |
15 |
Correct |
319 ms |
4996 KB |
Output is correct |
16 |
Correct |
311 ms |
3948 KB |
Output is correct |
17 |
Correct |
323 ms |
3948 KB |
Output is correct |
18 |
Correct |
249 ms |
5996 KB |
Output is correct |
19 |
Correct |
282 ms |
2796 KB |
Output is correct |
20 |
Correct |
293 ms |
4460 KB |
Output is correct |
21 |
Execution timed out |
2082 ms |
14572 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |