Submission #1281153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281153		Top1BUCODE	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	476 ms	49484 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define twt int t;cin>>t;while (t--)
#define i2 pair<int,int>
#define li pair<ll,int>
#define il pair<int,ll>
#define l2 pair<ll,ll>
#define pb push_back
const int lb=21,MASK=(1<<lb)+5;
int L,q;
ll scon[MASK],scha[MASK],toxic[MASK];
string s;
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//    freopen("JOI18SNAKES.inp","r",stdin);
    cin>>L>>q;
    for (int i=0;i<(1<<L);i++){
        char c;
        cin>>c;
        toxic[i]+=c-'0';
    }
    for (int mask=0;mask<(1<<L);mask++){
        scon[mask]=scha[mask]=toxic[mask];
    }
    for (int i=0;i<lb;i++){
        for (int mask=0;mask<(1<<lb);mask++){
            if (mask>>i&1) scon[mask]+=scon[mask^(1<<i)];
            else scha[mask]+=scha[mask^(1<<i)];
        }
    }
    for (int i=1;i<=q;i++){
        cin>>s;
        int maskO=0,maskP=0,maskQ=0;
        reverse(s.begin(),s.end());
        for (int j=0;j<s.size();j++){
            if (s[j]=='0') maskO|=(1<<j);
            if (s[j]=='1') maskP|=(1<<j);
            if (s[j]=='?') maskQ|=(1<<j);
        }
        ll ans;
        if (__builtin_popcount(maskQ)<=6){
            ans=toxic[maskP];
            for (int j=maskQ;j;j=(j-1)&maskQ){
                ans+=toxic[j^maskP];
            }
        }
        else if (__builtin_popcount(maskP)<=6){
            ans=scon[maskQ]*(__builtin_parity(maskP)?-1:1);
            for (int j=maskP;j;j=(j-1)&maskP){
                if (__builtin_parity(j^maskP)) ans-=scon[j|maskQ];
                else ans+=scon[j|maskQ];
            }
        }
        else {
            ans=scha[maskP];
            for (int j=maskO;j;j=(j-1)&maskO){
                if (__builtin_parity(j)) ans-=scha[j|maskP];
                else ans+=scha[j|maskP];
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

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