제출 #1268908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268908		MisterReaper	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	410 ms	24724 KiB

snake_escaping

// File A.cpp created on 11.09.2025 at 15:00:22
#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 L, Q;
    std::cin >> L >> Q;

    std::vector<int> A(1 << L);
    for (int i = 0; i < (1 << L); ++i) {
        char c;
        std::cin >> c;
        A[i] = int(c - '0');
    }

    std::vector<int> f = A;
    for (int i = 1; i < (1 << L); i <<= 1) {
        for (int j = 0; j < (1 << L); j += i << 1) {
            for (int k = 0; k < i; ++k) {
                f[i + j + k] += f[j + k];
            }
        }
    }

    std::vector<int> g = A;
    for (int i = 1; i < (1 << L); i <<= 1) {
        for (int j = 0; j < (1 << L); j += i << 1) {
            for (int k = 0; k < i; ++k) {
                g[j + k] += g[i + j + k];
            }
        }
    }

    debug(f);
    debug(g);

    std::vector<int> popcnt(1 << L);
    for (int i = 0; i < (1 << L); ++i) {
        popcnt[i] = 1 - 2 * __builtin_parity(i);
    }

    while (Q--) {
        std::string S;
        std::cin >> S;

        std::reverse(S.begin(), S.end());

        int msk0 = 0, msk1 = 0, mskq = 0;
        int cnt0 = 0, cnt1 = 0, cntq = 0;
        for (int i = 0; i < L; ++i) {
            if (S[i] == '0') {
                msk0 |= 1 << i;
                cnt0 += 1; 
            } else if (S[i] == '1') {
                msk1 |= 1 << i;
                cnt1 += 1;
            } else {
                mskq |= 1 << i;
                cntq += 1;
            }
        }

        i64 ans = 0;

        if (cnt0 <= cnt1 && cnt0 <= cntq) {
            for (int m = msk0; ; m = msk0 & (m - 1)) {
                ans += popcnt[m] * g[msk1 | m];
                if (m == 0) {
                    break;
                }
            }
        } else if (cnt1 <= cnt0 && cnt1 <= cntq) {
            for (int m = msk1; ; m = msk1 & (m - 1)) {
                ans += popcnt[msk1 ^ m] * f[mskq | m];
                if (m == 0) {
                    break;
                }
            }
        } else {
            for (int m = mskq; ; m = mskq & (m - 1)) {
                ans += A[msk1 | m];
                if (m == 0) {
                    break;
                }
            }
        }

        std::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