Submission #1289482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289482		ridarfx	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1560 ms	34308 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const long long mxN = 1e5+5;
const long long INF = 1e16;
const long long MOD = 1e9+7;
const long long LOG = 20;
const double eps = numeric_limits<double>::epsilon();
long long dp[1<<LOG];
void solve(){
    long long l,q;
    cin >> l >> q;
    string s;
    cin >> s;
    long long n = (1LL<<l);
    vector<long long> aa(n);
    for(int i=0; i<n; i++){
        aa[i]=s[i]-'0';
    }
    vector<long long> dpsup=aa, dpsub = aa;
    for(int i=0; i<l; i++){
        for(int mask=0; mask<n; mask++){
            if(mask&(1<<i)){
                dpsub[mask]+=dpsub[mask^(1<<i)];
            }
        }
    }
    for(int i=0; i<l; i++){
        for(int mask=0; mask<n; mask++){
            if(!(mask&(1<<i))){
                dpsup[mask]+=dpsup[mask^(1<<i)];
            }
        }
    }
    while(q--){
        string t;
        cin >> t;
        long long a=0, b=0, c=0;
        for(int i=0; i<l; i++){
            if(t[i]=='0'){
                a|=(1<<(l-i-1));
            }
            else if(t[i]=='1'){
                b|=(1<<(l-i-1));
            }
            else{
                c|=(1<<(l-i-1));
            }
        }
        long long ans = 0;
        long long zz = __builtin_popcountll(c);
        if(zz<=6){
            for(int sub=0; sub<(1<<zz); sub++){
                long long mask = b;
                long long cpos = 0;
                for(int i=0; i<l; i++){
                    if(c&(1<<(l-i-1))){
                        if(sub&(1<<cpos)){
                            mask|=(1<<(l-i-1));
                        }
                        cpos++;
                    }
                }
                ans+=aa[mask];
            }
        }
        else if(__builtin_popcountll(a)<=6){
            for(int sub=a; sub>=0; sub=(sub-1)&a){
                long long bits = __builtin_popcount(sub);
                long long val = dpsup[b|sub];
                if(bits%2){
                    ans-=val;
                }
                else ans+=val;
                if(sub==0)break;
            }
        }
        else{
            long long z = __builtin_popcountll(b);
            for(int sub=b; sub>=0; sub=(sub-1)&b){
                long long bits = __builtin_popcount(sub);
                long long val = dpsub[c|sub];
                if((z-bits)%2){
                    ans-=val;
                }
                else ans+=val;
                if(sub==0)break;
            }
        }
        cout << ans << endl;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long t = 1; //cin >> t;
    while(t--){
        solve();
    }
}

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