Submission #1218951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218951		vanea	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	405 ms	24848 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 1e6+10;

int a[mxN];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int l, q;
    cin >> l >> q;
    int n = (1 << l);
    vector<int> sub(n+1), sup(n+1), S(n+1), btcnt(n+1);
    for(int i = 0; i < n; i++) {
        char c; cin >> c;
        S[i] = c - '0';
        sub[i] = sup[i] = S[i];
        btcnt[i] = __builtin_popcount(i);
    }
    for(int i = 0; i < l; i++) {
        for(int m = 0; m < n; m++) {
            if(m & (1 << i)) {
                sub[m] += sub[m ^ (1 << i)];
            }
            else {
                sup[m] += sup[m ^ (1 << i)];
            }
        }
    }
    while(q--) {
        string s;
        cin >> s;
        int A = 0, B = 0, C = 0, cntA = 0, cntB = 0, cntC = 0;
        for(int i = 0; i < l; i++) {
            int now = (1 << (l - 1 - i));
            if(s[i] == '0') {
                A |= now;
                ++cntA;
            }
            else if(s[i] == '1') {
                B |= now;
                ++cntB;
            }
            else {
                C |= now;
                ++cntC;
            }
        }
        ll ans = 0;
        if(cntA <= cntB && cntA <= cntC) {
            for(int m = A; m != 0; m = (m - 1) & A) {
                ans += (1 - 2 * (btcnt[m] & 1)) * 1LL * sup[B|m];
            }
            ans += sup[B];
        }
        else if(cntC <= cntA && cntC <= cntB) {
            for(int m = C; m != 0; m = (m - 1) & C) {
                ans += S[B|m];
            }
            ans += S[B];
        }
        else {
            for(int m = B; m != 0; m = (m - 1) & B) {
                int now = (B|C)^m;
                ans += (1 - 2 * (btcnt[m] & 1)) * 1LL * sub[now];
            }
            ans += sub[C|B];
        }
        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