제출 #1137031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137031		Sharky	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2089 ms	41176 KiB

snake_escaping

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

#define int long long
#define fi first
#define se second

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(1 << n);
    vector<int> popcnt(1 << n);
    vector<int> d(1 << n, 0), u(1 << n, 0);
    for (int i = 0; i < (1 << n); i++) {
        char c;
        cin >> c;
        a[i] = c - '0';
        d[i] = u[i] = a[i];
        popcnt[i] = __builtin_popcount(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << n); j++) {
            if (j & (1 << i)) {
                d[j] += d[j ^ (1 << i)];
            } else u[j] += u[j ^ (1 << i)];
        }
    }
    while (q--) {
        string s;
        cin >> s;
        int zcnt = 0, ocnt = 0, qcnt = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '0') zcnt++;
            else if (s[i] == '1') ocnt++;
            else qcnt++;
        }        
        if (qcnt <= 6) {
            int ans = 0;
            for (int i = 0; i < (1 << qcnt); i++) {
                int cnt = 0, msk = 0;
                for (int j = 0; j < n; j++) {
                    msk *= 2;
                    if (s[j] == '?') {
                        msk += !!(i & (1 << cnt));
                        cnt++;
                    } else msk += (s[j] - '0');
                }
                ans += a[msk];
            }
            cout << ans << '\n';
            continue;
        }
        if (ocnt <= 6) {
            int ans = 0, om = 0, qm = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == '1') om |= (1 << (n - i - 1));
                if (s[i] == '?') qm |= (1 << (n - i - 1));
            }
            for (int m = om;; m = (m - 1) & om) {
                ans += ((ocnt % 2 != popcnt[m] % 2) ? -1 : 1) * d[m + qm];
                if (!m) break;
            }
            cout << ans << '\n';
            continue;
        }
        if (zcnt <= 6) {
            int ans = 0, zm = 0, om = 0, qm = 0;
            for (int i = 0; i < n; i++) {
                if (s[i] == '0') zm |= (1 << (n - i - 1));
                if (s[i] == '1') om |= (1 << (n - i - 1));
                if (s[i] == '?') qm |= (1 << (n - i - 1));
            }
            for (int m = zm;; m = (m - 1) & zm) {
                ans += ((popcnt[m ^ zm] % 2) ? -1 : 1) * u[(om | (m ^ zm))];
                if (!m) break;
            }
            cout << ans << '\n';
            continue;
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int test = 1;
    // cin >> test;
    while (test--) solve();
}

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