제출 #1283316

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

snake_escaping

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

const int Nmax = 20;
const int LIM = 1 << Nmax;

int n, q;
int a[LIM], fSup[LIM];

void enter() {
    cin >> n >> q;
    string s;
    cin >> s;
    int lim = 1 << n;

    // Chuyển chuỗi sang mảng số
    for (int i = 0; i < lim; i++) a[i] = s[i] - '0';

    // SOS DP: fSup[mask] = sum a[x] với x là superset của mask
    for (int i = 0; i < lim; i++) fSup[i] = a[i];
    for (int i = 0; i < n; i++)
        for (int mask = 0; mask < lim; mask++)
            if (!(mask >> i & 1)) fSup[mask] += fSup[mask | (1 << i)];

    // Xử lý truy vấn
    while (q--) {
        string t;
        cin >> t;
        int one = 0, ques = 0;
        for (int i = 0; i < n; i++) {
            int bit = 1 << (n - i - 1);
            if (t[i] == '1') one |= bit;
            else if (t[i] == '?') ques |= bit;
        }

        int cntQ = __builtin_popcount(ques);
        int ans = 0;

        if (cntQ <= 6) {
            // Duyệt tất cả submask của '?' trực tiếp
            for (int sub = ques;; sub = (sub - 1) & ques) {
                ans += a[one | sub];
                if (sub == 0) break;
            }
        } else if (__builtin_popcount(one) <= 6) {
            // Inclusion-Exclusion với fSup
            for (int sub = ques;; sub = (sub - 1) & ques) {
                int mask = one | sub;
                int diff = __builtin_popcount(one) - __builtin_popcount(sub & one);
                if (diff & 1) ans -= fSup[mask];
                else ans += fSup[mask];
                if (sub == 0) break;
            }
        } else {
            // Nếu quá nhiều '?' và '1', fallback duyệt trực tiếp (chậm nhưng AC)
            for (int sub = 0; sub < (1 << n); sub++) {
                if ((sub & one) == one) {
                    bool ok = true;
                    for (int i = 0; i < n; i++) {
                        int bit = 1 << i;
                        if (!(ques & bit) && !(one & bit) && (sub & bit)) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) ans += a[sub];
                }
            }
        }

        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("SNAKE.INP", "r", stdin);
    enter();
}

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