Submission #1275723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275723		MisterReaper	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	473 ms	26048 KiB

snake_escaping

// File snakeescaping.cpp created on 03.10.2025 at 10:26:25
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

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

    int N, Q;
    std::cin >> N >> Q;

    std::string S;
    std::cin >> S;

    std::vector<int> v(1 << N);
    for (int i = 0; i < (1 << N); ++i) {
        v[i] = int(S[i] - '0');
    }

    std::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--) {
        std::string T;
        std::cin >> T;

        std::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;
                }
            }
            std::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;
                }
            }
            std::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;
                }
            }
            std::cout << ans << '\n';
        }
        debug();
    }

    return 0;
}

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