Submission #1306167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306167		uranium235	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	398 ms	20924 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int bits = 6;
const int mod = 1'000'000'007;

template <class a, class b> ostream& operator<<(ostream &l, const pair<a, b> &r) {
    l << "(" << r[0] << ", " << r.second << ")";
    return l;
}

template <class t, unsigned long int s> ostream& operator<<(ostream &l, const array<t, s> &r) {
    l << "[";
    for (int i = 0; i + 1 < s; i++) l << r[i] << ", ";
    if (s > 0) l << r[s - 1];
    l << "]";
    return l;
}

template <class t> ostream& operator<<(ostream &l, const vector<t> &r) {
    l << "{";
    for (int i = 0; i + 1 < r.size(); i++) l << r[i] << ", ";
    if (!r.empty()) l << r.back();
    l << "}";
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;

    vector<int> a(1 << n), sos(1 << n), oso(1 << n);
    for (int i = 0; i < (1 << n); i++) {
        char c;
        cin >> c;
        a[i] = c - '0';
    }
    sos = a;
    oso = a;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << n); j++) {
            if (j & (1 << i)) {
                sos[j] += sos[j ^ (1 << i)];
            } else {
                oso[j] += oso[j ^ (1 << i)];
            }
        }
    }

    for (int i = 0; i < q; i++) {
        string s;
        cin >> s;
        int zeroes = 0, ones = 0, qs = 0;
        for (int j = 0; j < n; j++) {
            if (s[n - 1 - j] == '0') zeroes |= 1 << j;
            else if (s[n - 1 - j] == '1') ones |= 1 << j;
            else qs |= 1 << j;
        }

        int ans = 0;
        if (__builtin_popcount(zeroes) <= 6) {
            for (int j = zeroes; j > 0; j = (j - 1) & zeroes) {
                ans += oso[ones | j] * (__builtin_parity(j) ? -1 : 1);
            }
            ans += oso[ones];
        } else if (__builtin_popcount(ones) <= 6) {
            for (int j = ones; j > 0; j = (j - 1) & ones) {
                ans += sos[qs | j] * (__builtin_parity(j ^ ones) ? -1 : 1 );
            }
            ans += sos[qs] * (__builtin_parity(ones) ? -1 : 1);
        } else {
            for (int j = qs; j > 0; j = (j - 1) & qs) {
                ans += a[ones | j];
            }
            ans += a[ones];
        }
        cout << ans << '\n';
    }
}

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