Submission #80187

#	Time	Username	Problem	Language	Result	Execution time	Memory
80187		Bodo171	Snake Escaping (JOI18_snake_escaping)	C++14	5 / 100	1867 ms	66560 KiB

snake_escaping

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25