Submission #391765

#	Time	Username	Problem	Language	Result	Execution time	Memory
391765		timmyfeng	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1012 ms	43272 KiB

snake_escaping

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

const int N = 20;

int zero[1 << N], one[1 << N], value[1 << N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    string s;
    cin >> n >> q >> s;

    for (int i = 0; i < (1 << n); ++i) {
        zero[i] = one[i] = value[i] = s[i] - '0';
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (1 << n); ++j) {
            if ((j & (1 << i)) > 0) {
                one[j ^ (1 << i)] += one[j];
            } else {
                zero[j ^ (1 << i)] += zero[j];
            }
        }
    }

    while (q--) {
        cin >> s;

        reverse(s.begin(), s.end());

        int mask_0 = 0, mask_1 = 0, mask_q = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == '0') {
                mask_0 |= 1 << i;
            } else if (s[i] == '1') {
                mask_1 |= 1 << i;
            } else {
                mask_q |= 1 << i;
            }
        }

        int ans = 0;
        if (__builtin_popcount(mask_0) <= n / 3) {
            ans = one[mask_1];
            for (int i = mask_0; i > 0; i = mask_0 & (i - 1)) {
                if (__builtin_parity(i) == 1) {
                    ans -= one[mask_1 ^ i];
                } else {
                    ans += one[mask_1 ^ i];
                }
            }
        } else if (__builtin_popcount(mask_1) <= n / 3) {
            ans = zero[mask_1 ^ mask_q];
            for (int i = mask_1; i > 0; i = mask_1 & (i - 1)) {
                if (__builtin_parity(i) == 1) {
                    ans -= zero[mask_q ^ mask_1 ^ i];
                } else {
                    ans += zero[mask_q ^ mask_1 ^ i];
                }
            }
        } else {
            ans = value[mask_1];
            for (int i = mask_q; i > 0; i = mask_q & (i - 1)) {
                ans += value[mask_1 ^ i];
            }
        }

        cout << ans << "\n";
    }
}

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