Submission #702543

#	Time	Username	Problem	Language	Result	Execution time	Memory
702543		bebra	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	761 ms	20580 KiB

snake_escaping

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

#define dbg(x) cerr << #x << ": " << x << endl;


constexpr int MAX_BIT = 20;
constexpr int MAX_N = 1 << 20;
constexpr int MAGIC = 6;

int dp_sub[MAX_N];
int dp_super[MAX_N];


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

    int k, q;
    cin >> k >> q;

    string s;
    cin >> s;

    for (int mask = 0; mask < (1 << k); ++mask) {
        dp_sub[mask] = s[mask] - '0';
        dp_super[mask] = s[mask] - '0';
    }
    for (int bit = 0; bit < k; ++bit) {
        for (int mask = 0; mask < (1 << k); ++mask) {
            if (mask & (1 << bit)) {
                dp_sub[mask] += dp_sub[mask ^ (1 << bit)];
            } else {
                dp_super[mask] += dp_super[mask ^ (1 << bit)];
            }
        }
    }

    while (q--) {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());

        int cnt_null = 0;
        int cnt_one = 0;
        int cnt_mark = 0;
        int mask_null = 0;
        int mask_one = 0;
        int mask_mark = 0;
        for (int i = 0; i < k; ++i) {
            if (t[i] == '0') {
                ++cnt_null;
                mask_null |= 1 << i;
            } else if (t[i] == '1') {
                ++cnt_one;
                mask_one |= 1 << i;
            } else {
                ++cnt_mark;
                mask_mark |= 1 << i;
            }
        }

        int res = 0;
        if (cnt_null <= MAGIC) {
            res = dp_super[mask_one];
            for (int submask = mask_null; submask > 0; submask = (submask - 1) & mask_null) {
                int sign = (__builtin_popcount(submask) % 2 == 0 ? 1 : -1);
                res += dp_super[submask | mask_one] * sign;
            }
        } else if (cnt_one <= MAGIC) {
            res = dp_sub[mask_mark | mask_one];
            for (int submask = mask_one; submask > 0; submask = (submask - 1) & mask_one) {
                int sign = (__builtin_popcount(submask) % 2 == 0 ? 1 : -1);
                res += dp_sub[(submask ^ mask_one) | mask_mark] * sign;
            }
        } else {
            res = s[mask_one] - '0';
            for (int submask = mask_mark; submask > 0; submask = (submask - 1) & mask_mark) {
                res += s[submask | mask_one] - '0';
            }
        }

        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