Submission #785399

#	Time	Username	Problem	Language	Result	Execution time	Memory
785399		Denkata	Snake Escaping (JOI18_snake_escaping)	C++17	0 / 100	1 ms	340 KiB

snake_escaping

#include<bits/stdc++.h>
#define endl '\n'
#pragma GCC optimize("Ofast")
using namespace std;
string s,val;
int i,j,p,q,n,m,k,l,Q,A,B,C;
int dp[(1<<21)],subdp[(1<<21)];
int bitcnt[(1<<21)],ans;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>l>>Q;
    n = (1<<l);
    cin>>val;
    for(i=1; i<n; i++)
        bitcnt[i] = bitcnt[i/2]+i%2;
    for(i=0; i<n; i++)
        dp[i] = subdp[i] =  val[i]-'0';
    for(i=0; i<l; i++)
    {
        for(j=0; j<n; j++)
        {
            if((j&(1<<i))==0)
                dp[j]+=dp[j^(1<<i)];
            else subdp[j]+=subdp[j^(1<<i)];
            ///1 za sub/ 0 za super
        }
    }
    while(Q--)
    {
        cin>>s;
        A = B = C = 0;
        ans = 0;
        for(i=0; i<l; i++)
        {
            if(s[i]=='0')
                A |= (1<<(l-i-1));
            else if(s[i]=='1')
                B |= (1<<(l-i-1));
            else
                C |= (1<<(l-i-1));

        }
        ///tva e mega dobro
        if(bitcnt[C]<=bitcnt[A] && bitcnt[C]<=bitcnt[B])
        {
            ///vsichki podmnojestva ot setnatite bitove na C
            for(int m=C; m!=0; m=(m-1)&C)
            {
                ans+=val[m|B]-'0';
            }
            ans+=val[B]-'0';
        }
        ///tva e mega dobro
        else if(bitcnt[A]<bitcnt[B])
        {
            for(int m=A;m!=0;m=(m-1)&A)
            {
                if(bitcnt[m]%2==0)
                    ans+=dp[m|B];
                else
                    ans-=dp[m|B];
            }
            ans+=dp[B];
        }
        else
        {
            for(int m=B;m!=0;m=(m-1)&B)
            {
                if((bitcnt[B]-bitcnt[m])%2==0)
                    ans+=subdp[m|C];
                else
                    ans-=subdp[m|C];
            }
            ans+=subdp[C];
        }
        cout<<ans<<endl;

    }
    return 0;
}
///precompute bit count for speed up

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