Submission #1312486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312486		qiwejfpsdiaj	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1534 ms	17836 KiB

snake_escaping

#include <iostream>
#include <array>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

int main() {
    int L, Q;
    std::cin >> L >> Q;
    std::string S;
    std::cin >> S;

    std::vector<int> sub(1 << L), sup(1 << L);
    for (int i = 0; i < 1 << L; i++)
        sub[i] = sup[i] = S[i] - '0';

    for (int i = 0; i < L; i++) {
        for (int mask = 0; mask < 1 << L; mask++) {
            if (mask >> i & 1) sub[mask] += sub[mask ^ (1 << i)];
            else sup[mask] += sup[mask ^ (1 << i)];
        }
    }

    while (Q--) {
        std::string T;
        std::cin >> T;
        std::reverse(T.begin(), T.end());

        std::array<int, 3> freq = {};
        int fixed = 0, vary = 0;
        for (int i = 0; i < L; i++) {
            if (T[i] == '0') {
                freq[0]++;
            } else if (T[i] == '1') {
                freq[1]++;
                fixed += 1 << i;
            } else {
                freq[2]++;
                vary += 1 << i;
            }
        }

        std::pair<int, int> mn = {L + 1, 0};
        for (int i = 0; i < 3; i++)
            mn = std::min(mn, std::make_pair(freq[i], i));

        int res = 0;
        if (mn.second == 0) {
            fixed += vary;
            vary = (1 << L) - 1 - vary;
            for (int s = fixed; s < 1 << L; ++s |= fixed) {
                int sgn = __builtin_popcount(s - fixed) & 1 ? -1 : 1;
                res += sgn * sup[s & vary];
            }
        } else if (mn.second == 1) {
            for (int s = fixed; ; --s &= fixed) {
                int sgn = __builtin_popcount(fixed - s) & 1 ? -1 : 1;
                res += sgn * sub[s | vary];
                if (s == 0) break;
            }
        } else {
            for (int s = vary; ; --s &= vary) {
                res += S[s + fixed] - '0';
                if (s == 0) break;
            }
        }
        std::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