Submission #1058837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058837		BF001	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	439 ms	43368 KiB

snake_escaping

#include<bits/stdc++.h>
using namespace std;
 
#define N 25

int n, q, dp1[(1 << 20) + 1], dp2[(1 << 20) + 1], val[(1 << 20) + 1];
string s;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> q;
    cin >> s;
    for (int i = 0; i < (1 << n); i++){
        dp1[i] = dp2[i] = val[i] = (s[i] - '0');
    }

    for (int i = 0; i < n; i++){
        for (int msk = 0; msk < 1 << n; msk++){
            if ((msk >> i) & 1){
                dp1[msk] += dp1[msk ^ (1 << i)];
            }
            else dp2[msk] += dp2[msk ^ (1 << i)];
        }
    }

    while (q--){
        string t;
        cin >> t;
        reverse(t.begin(), t.end());
        int cnt1 = 0, cnta = 0, cnt0 = 0, mska = 0, msk1 = 0, msk0 = 0;
        for (int i = 0; i < (int) t.size(); i++){
            if (t[i] == '?'){
                cnta++;
                mska |= (1 << i);
                continue;
            }
            if (t[i] == '1'){
                cnt1++;
                msk1 |= (1 << i);
                continue;
            }
            cnt0++;
            msk0 |= (1 << i);
        }
        int mi = min({cnt0, cnt1, cnta});
        if (cnta == mi){
            int res = val[msk1];
            for (int msk = mska; msk > 0; msk = (msk - 1) & mska){
                res += val[msk1 | msk];
            }
            cout << res << "\n";
            continue;
        }
        if (mi == cnt0){
            int res = dp2[msk1];
            for (int msk = msk0; msk > 0; msk = (msk - 1) & msk0){
                if (__builtin_popcount(msk) % 2 == 0){
                    res += dp2[msk1 | msk];
                }
                else res -= dp2[msk1 | msk];
            }
            cout << res << "\n";
            continue;
        }
        int res = dp1[mska];
        if (cnt1 & 1) res = -dp1[mska];
        for (int msk = msk1; msk > 0; msk = (msk - 1) & msk1){
            if (__builtin_popcount(msk) % 2 == cnt1 % 2){
                res += dp1[mska | msk];
            }
            else res -= dp1[mska | msk];
        }
        cout << res << "\n";
    }
 
    return 0;
}

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