제출 #1283322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283322		dat	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	379 ms	21888 KiB

snake_escaping

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

const int Nmax = 20;
int n, q;
int a[1 << Nmax], f[1 << Nmax], f0[1 << Nmax];

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

    cin >> n >> q;
    string s;
    cin >> s;

    int lim = 1 << n;
    for (int i = 0; i < lim; i++)
        a[i] = f[i] = f0[i] = s[i] - '0';

    // DP SOS
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < lim; mask++) {
            if (mask & (1 << i)) f[mask] += f[mask ^ (1 << i)];
            else f0[mask] += f0[mask ^ (1 << i)];
        }
    }

    while (q--) {
        cin >> s;
        reverse(s.begin(), s.end()); // bit 0 = LSB

        int one = 0, zero = 0, ques = 0;
        for (int i = 0; i < n; i++) {
            int bit = 1 << i;
            if (s[i] == '1') one |= bit;
            else if (s[i] == '0') zero |= bit;
            else ques |= bit;
        }

        int ans = 0;

        if (__builtin_popcount(ques) <= 6) {
            // trực tiếp lặp submask
            for (int sub = ques;; sub = (sub - 1) & ques) {
                ans += a[sub | one];
                if (sub == 0) break;
            }
        }
        else if (__builtin_popcount(one) <= 6) {
            // Inclusion-Exclusion trên mask one
            ans = f[ques] * (__builtin_parity(one) ? -1 : 1);
            for (int sub = one; sub; sub = (sub - 1) & one) {
                if (__builtin_parity(sub) ^ __builtin_parity(one)) ans -= f[sub | ques];
                else ans += f[sub | ques];
            }
        }
        else if (__builtin_popcount(zero) <= 6) {
            // Inclusion-Exclusion trên mask zero (SuperSOS)
            ans = f0[one];
            for (int sub = zero; sub; sub = (sub - 1) & zero) {
                if (__builtin_parity(sub)) ans -= f0[sub | one];
                else ans += f0[sub | one];
            }
        }

        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