Submission #591013

#	Time	Username	Problem	Language	Result	Execution time	Memory
591013		piOOE	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	827 ms	44652 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int L = 20;

int S[1 << L], A[1 << L], B[1 << L], popcnt[1 << L];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 1; i < 1 << L; ++i) {
        popcnt[i] = popcnt[i - (i & -i)] + 1;
    }
    int l, q;
    string s;
    cin >> l >> q >> s;
    for (int i = 0; i < 1 << l; ++i) {
        S[i] = A[i] = B[((1 << l) - 1) ^ i] = s[i] - '0';
    }
    for (int i = 0; i < l; ++i) {
        for (int mask = 0; mask < 1 << l; ++mask) {
            if (mask & 1 << i) {
                A[mask] += A[mask ^ 1 << i];
            }
        }
    }
    for (int i = 0; i < l; ++i) {
        for (int mask = 0; mask < 1 << l; ++mask) {
            if (mask & 1 << i) {
                B[mask] += B[mask ^ 1 << i];
            }
        }
    }
    while (q--) {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());
        int mask0 = 0, mask1 = 0, mask2 = 0;
        for (int i = 0; i < l; ++i) {
            if (t[i] == '0') {
                mask0 ^= 1 << i;
            } else if (t[i] == '1') {
                mask1 ^= 1 << i;
            } else {
                mask2 ^= 1 << i;
            }
        }
        int ans = 0;
        if (popcnt[mask1] <= 6) {
            for (int mask = mask1; mask; mask = (mask - 1) & mask1) {
                ans += A[mask ^ mask2] * (popcnt[mask ^ mask1] & 1 ? -1 : 1);
            }
            ans += A[mask2] * (popcnt[mask1] & 1 ? -1 : 1);
        } else if (popcnt[mask0] <= 6) {
            for (int mask = mask0; mask; mask = (mask - 1) & mask0) {
                ans += B[mask ^ mask2] * (popcnt[mask ^ mask0] & 1 ? -1 : 1);
            }
            ans += B[mask2] * (popcnt[mask0] & 1 ? -1 : 1);
        } else {
            for (int mask = mask2; mask; mask = (mask - 1) & mask2) {
                ans += S[mask ^ mask1];
            }
            ans += S[mask1];
        }
        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