Submission #1276720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276720		coderg300711	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	448 ms	26032 KiB

snake_escaping

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

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

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

    string s;
    cin >> s;

    vector<int> v(1 << n);
    for (int i = 0; i < (1 << n); ++i) {
        v[i] = int(s[i] - '0');
    }

    vector<int> sp(1 << n), sb(1 << n), pp(1 << n);
    for (int i = 0; i < (1 << n); ++i) {
        sp[i] = v[i];
        sb[i] = v[i];
    }
    for (int i = 1; i < (1 << n); i <<= 1) {
        for (int j = 0; j < (1 << n); j += i << 1) {
            for (int k = 0; k < i; ++k) {
                sp[j + k] += sp[i + j + k];
                sb[i + j + k] += sb[j + k];
            }
        }
    }
    pp[0] = +1;
    for (int i = 1; i < (1 << n); ++i) {
        pp[i] = pp[i ^ (i & -i)] * -1;
    }

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

        int cnt0 = 0, cnt1 = 0, cntq = 0;
        for (int i = 0; i < n; ++i) {
            if (t[i] == '0') {
                cnt0 += 1;
            } else if (t[i] == '1') {
                cnt1 += 1;
            } else {
                cntq += 1;
            }
        }

        if (cntq <= cnt0 && cntq <= cnt1) {
            int msk = 0, init = 0;
            for (int i = 0; i < n; ++i) {
                if (t[i] == '?') {
                    msk |= 1 << i;
                } else if (t[i] == '1') {
                    init |= 1 << i;
                }
            }
            int ans = 0;
            for (int m = msk; ; m = (m - 1) & msk) {
                ans += v[m | init];
                if (m == 0) {
                    break;
                }
            }
            cout << ans << '\n';
        } else if (cnt0 <= cnt1 && cnt0 <= cntq) {
            int msk = 0, init = 0;
            for (int i = 0; i < n; ++i) {
                if (t[i] == '0') {
                    msk |= 1 << i;
                } else if (t[i] == '1') {
                    init |= 1 << i;
                }
            }
            int ans = 0;
            for (int m = msk; ; m = (m - 1) & msk) {
                ans += pp[m] * sp[m | init];
                if (m == 0) {
                    break;
                }
            }
            cout << ans << '\n';
        } else {
            int msk = 0, init = 0;
            for (int i = 0; i < n; ++i) {
                if (t[i] == '1') {
                    msk |= 1 << i;
                } else if (t[i] == '?') {
                    init |= 1 << i;
                }
            }
            int ans = 0;
            for (int m = msk; ; m = (m - 1) & msk) {
                ans += pp[m] * sb[(msk ^ m) | init];
                if (m == 0) {
                    break;
                }
            }
            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