This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int dp[(1 << 20)][20][2];
int br[(1 << 20)][2];
void sos(int x) {
for(int i = 0; i < (1 << 20); i++) {
dp[i][0][x] = br[i][x];
if(i%2) {
dp[i][0][x]+=br[i-1][x];
}
for(int j = 1; j < 20; j++) {
dp[i][j][x] = dp[i][j-1][x];
if(i&(1 << j)) {
dp[i][j][x]+=dp[i-(1 << j)][j-1][x];
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int l,q;
cin >> l >> q;
for(int i = 0; i < (1 << 20); i++) {
br[i][0] = 0;
br[i][1] = 0;
}
for(int i = 0; i < (1 << l); i++) {
char a;
cin >> a;
br[i][0] = a-'0';
br[(1 << 20)-1-i][1] = a-'0';
}
//sos(0);
//sos(1);
for(int i = 0; i < q; i++) {
vector<int> wow(20);
int br0 = 20-l,br1 = 0,br2 = 0,ans = 0;
for(int j = l-1; j >= 0; j--) {
char a;
cin >> a;
if(a == '?') {
wow[j] = 2;
}
else {
wow[j] = a-'0';
}
if(wow[j] == 0) {
br0++;
}
else if(wow[j] == 1) {
br1++;
}
else {
br2++;
}
}
if(true) {
int x = 0,y = 0,c;
for(int j = 0; j < 20; j++) {
if(wow[j] == 1) {
x+=(1 << j);
}
if(wow[j] == 2) {
y+=(1 << j);
}
}
c = y;
while(true) {
// cout << x << " " << c << endl;
ans+=br[x+c][0];
if(c == 0) {
break;
}
c = (c-1)&y;
}
cout << ans << "\n";
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |