제출 #1283315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283315		dat	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	1 ms	568 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], fSub[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 chuẩn
    // 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)];
    
    // fSub[mask] = sum a[x] với x là subset của mask
    for (int i = 0; i < lim; i++) fSub[i] = a[i];
    for (int i = 0; i < n; i++)
        for (int mask = 0; mask < lim; mask++)
            if (mask >> i & 1) fSub[mask] += fSub[mask ^ (1 << i)];
    
    // Xử lý truy vấn
    while (q--) {
        string t;
        cin >> t;
        int one = 0, zero = 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] == '0') zero |= bit;
            else ques |= bit;
        }

        int ans = 0;
        int cntQ = __builtin_popcount(ques);
        int cntOne = __builtin_popcount(one);
        int cntZero = __builtin_popcount(zero);

        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[sub | one];
                if (sub == 0) break;
            }
        } else if (cntOne <= 6) {
            // Inclusion-Exclusion dùng fSup
            for (int sub = ques;; sub = (sub - 1) & ques) {
                int mask = one | sub;
                int diff = cntOne - __builtin_popcount(sub);
                if (diff & 1) ans -= fSup[mask];
                else ans += fSup[mask];
                if (sub == 0) break;
            }
        } else if (cntZero <= 6) {
            // Inclusion-Exclusion dùng fSub
            for (int sub = ques;; sub = (sub - 1) & ques) {
                int mask = sub | zero; // zero cố định
                int diff = __builtin_popcount(sub);
                if (diff & 1) ans -= fSub[mask];
                else ans += fSub[mask];
                if (sub == 0) break;
            }
        }

        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