Submission #1308967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308967		wangzhiyi33	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1834 ms	33156 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define fir first
#define sec second
#define pb push_back
#pragma GCC optimize("O3,unroll-loops")

int n,qu;
int a[(1<<20)];
int sos[(1<<20)],sps[(1<<20)];

int hmm(int a){
    int brp=0;
    for(int q=0;q<=20;q++){
        if((a>>q)&1){
            brp++;
        }
    }
    if(brp%2==0)return 1;
    return -1;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>qu;
    for(int q=0;q<(1<<n);q++){
        char x; cin>>x;
        a[q]=x-'0'; 
        sos[q]=sps[q]=a[q];
    }
    
    for(int q=0;q<n;q++){
        for(int w=0;w<(1<<n);w++){
            if((w>>q)&1){
                sos[w]+=sos[w^(1<<q)];
            }
            else{
                sps[w]+=sps[w^(1<<q)];
            }
        }
    }

    while(qu--){
        string s; cin>>s;
        int nol=0,satu=0,ga=0;
        for(int q=0;q<n;q++){
            if(s[n-q-1]=='0')nol+=(1<<q);
            else if(s[n-q-1]=='1')satu+=(1<<q);
            else ga+=(1<<q);
        }

        if(__builtin_popcount(nol)<=6){
            int ans=sps[satu];
            for(int q=nol;q>0;q=(q-1)&nol){
                ans+=hmm(q)*sps[satu | q];
            }

            cout<<ans<<endl;
        }
        else if(__builtin_popcount(satu)<=6){
            int ans=0;
            for(int q=satu;q>0;q=(q-1)&satu){
                ans+=hmm(q ^ satu)*sos[q | ga];
            }
            ans+=hmm(satu)*sos[ga];
            cout<<ans<<endl;
        }
        else{
            int ans=a[satu];
            for(int q=ga;q>0;q=ga & (q-1)){
                ans+=a[satu | q];
            }
            cout<<ans<<endl;
        }
    }
}

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