#include <iostream>
#include <fstream>
using namespace std;
const int nmax=(1<<20)+5;
string s;
char t;
int pc[nmax],sub[nmax],supra[nmax],v[nmax];
int l,q,i,j,m0,m1,mq,mn,ans;
bool brk;
int main()
{
// freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>l>>q;
cin>>s;
for(i=0;i<(1<<l);i++)
{
if(i!=0)
pc[i]=pc[(i&(i-1))]+1;
sub[i]=supra[i]=v[i]=s[i]-'0';
}
for(i=0;i<l;i++)
for(j=0;j<(1<<l);j++)
if(((1<<i)&j))
sub[j]+=sub[(j^(1<<i))];
for(i=0;i<l;i++)
for(j=(1<<l)-1;j>=0;j--)
if(!((1<<i)&j))
supra[j]+=supra[(j^(1<<i))];
for(int cnt=1;cnt<=q;cnt++)
{
cin>>s;
m0=m1=mq=0;
for(j=l-1;j>=0;j--)
{
t=s[l-1-j];
if(t=='0') m0+=(1<<j);
if(t=='1') m1+=(1<<j);
if(t=='?') mq+=(1<<j);
}
mn=min(min(pc[m0],pc[m1]),pc[mq]);
ans=0;brk=0;
if(mn==pc[m0])
{
ans=supra[m1];
i=m0;
while(i!=0)
{
if((pc[i]&1)) ans-=supra[(i|m1)];
else ans+=supra[(i|m1)];
i=((i-1)&m0);
}
}
else
{
if(mn==pc[m1])
{
i=m1;
while(!brk)
{
if(i==0)
brk=1;
if(((pc[m1]-pc[i])&1)) ans-=sub[(i|mq)];
else ans+=sub[(i|mq)];
i=((i-1)&m1);
}
}
else
{
i=mq;
while(!brk)
{
ans+=v[(m1|i)];
if(i==0)
brk=1;
i=((i-1)&mq);
}
}
}
cout<<ans<<'\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
672 KB |
Output is correct |
| 4 |
Correct |
4 ms |
672 KB |
Output is correct |
| 5 |
Correct |
4 ms |
728 KB |
Output is correct |
| 6 |
Correct |
4 ms |
800 KB |
Output is correct |
| 7 |
Correct |
4 ms |
808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
840 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
672 KB |
Output is correct |
| 4 |
Correct |
4 ms |
672 KB |
Output is correct |
| 5 |
Correct |
4 ms |
728 KB |
Output is correct |
| 6 |
Correct |
4 ms |
800 KB |
Output is correct |
| 7 |
Correct |
4 ms |
808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
840 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
864 KB |
Output is correct |
| 11 |
Correct |
1814 ms |
15736 KB |
Output is correct |
| 12 |
Correct |
1767 ms |
26252 KB |
Output is correct |
| 13 |
Correct |
1859 ms |
36176 KB |
Output is correct |
| 14 |
Correct |
1859 ms |
46984 KB |
Output is correct |
| 15 |
Correct |
1867 ms |
58760 KB |
Output is correct |
| 16 |
Runtime error |
1801 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
672 KB |
Output is correct |
| 4 |
Correct |
4 ms |
672 KB |
Output is correct |
| 5 |
Correct |
4 ms |
728 KB |
Output is correct |
| 6 |
Correct |
4 ms |
800 KB |
Output is correct |
| 7 |
Correct |
4 ms |
808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
840 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
864 KB |
Output is correct |
| 11 |
Correct |
1814 ms |
15736 KB |
Output is correct |
| 12 |
Correct |
1767 ms |
26252 KB |
Output is correct |
| 13 |
Correct |
1859 ms |
36176 KB |
Output is correct |
| 14 |
Correct |
1859 ms |
46984 KB |
Output is correct |
| 15 |
Correct |
1867 ms |
58760 KB |
Output is correct |
| 16 |
Runtime error |
1801 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
672 KB |
Output is correct |
| 4 |
Correct |
4 ms |
672 KB |
Output is correct |
| 5 |
Correct |
4 ms |
728 KB |
Output is correct |
| 6 |
Correct |
4 ms |
800 KB |
Output is correct |
| 7 |
Correct |
4 ms |
808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
840 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
864 KB |
Output is correct |
| 11 |
Runtime error |
181 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
4 ms |
572 KB |
Output is correct |
| 3 |
Correct |
4 ms |
672 KB |
Output is correct |
| 4 |
Correct |
4 ms |
672 KB |
Output is correct |
| 5 |
Correct |
4 ms |
728 KB |
Output is correct |
| 6 |
Correct |
4 ms |
800 KB |
Output is correct |
| 7 |
Correct |
4 ms |
808 KB |
Output is correct |
| 8 |
Correct |
4 ms |
840 KB |
Output is correct |
| 9 |
Correct |
4 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
864 KB |
Output is correct |
| 11 |
Correct |
1814 ms |
15736 KB |
Output is correct |
| 12 |
Correct |
1767 ms |
26252 KB |
Output is correct |
| 13 |
Correct |
1859 ms |
36176 KB |
Output is correct |
| 14 |
Correct |
1859 ms |
46984 KB |
Output is correct |
| 15 |
Correct |
1867 ms |
58760 KB |
Output is correct |
| 16 |
Runtime error |
1801 ms |
66560 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 17 |
Halted |
0 ms |
0 KB |
- |
