Submission #934936

#	Time	Username	Problem	Language	Result	Execution time	Memory
934936		MinaRagy06	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1714 ms	50516 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int dp[2][1 << 20], dp2[2][1 << 20];
string s;
int a[1 << 20];
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n, q;
    cin >> n >> q;
    int m = n;
    n = 1 << n;
    for (int i = 0; i < n; i++) {
        char c;
        cin >> c;
        a[i] = c - '0';
    }
    for (int i = 0; i < n; i++) dp[m & 1][i] = a[i], dp2[m & 1][i] = a[i];
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            dp[i & 1][j] = dp[(i + 1) & 1][j];
            dp2[i & 1][j] = dp2[(i + 1) & 1][j];
            if ((j >> i) & 1) {
                dp[i & 1][j] += dp[(i + 1) & 1][j ^ (1 << i)];
            } else {
                dp2[i & 1][j] += dp2[(i + 1) & 1][j ^ (1 << i)];
            }
        }
    }
    while (q--) {
        cin >> s;
        int frq[3]{};
        for (int i = 0; i < m; i++) {
            if (s[i] == '?') {
                frq[2]++;
            } else {
                frq[s[i] - '0']++;
            }
        }
        reverse(s.begin(), s.end());
        int ans = 0;
        if (frq[2] <= frq[0] && frq[2] <= frq[1]) {
            for (int msk = 0; msk < (1 << frq[2]); msk++) {
                int cur = 0;
                int v = 0;
                for (int i = 0; i < m; i++) {
                    int b = s[i] - '0';
                    if (s[i] == '?') {
                        b = (msk >> (cur++)) & 1;
                    }
                    v += b << i;
                }
                ans += a[v];
            }
        } else if (frq[1] <= frq[0] && frq[1] <= frq[2]) {
            int x = 0, st = 0;
            for (int i = 0; i < m; i++) {
                int b = s[i] - '0';
                if (s[i] == '?') b = 1;
                if (s[i] == '1') st += 1 << i, b = 0;
                x += b << i;
            }
            for (int msk = st; msk >= 0; msk = ((msk - 1) & st)) {
                int v = x | msk;
                int cnt = __builtin_popcount(msk);
                if ((frq[1] - cnt) & 1) {
                    ans -= dp[0][v];
                } else {
                    ans += dp[0][v];
                }
                if (!msk) break;
            }
        } else {
            int x = 0, st = 0;
            for (int i = 0; i < m; i++) {
                int b = s[i] - '0';
                if (s[i] == '?') b = 0;
                if (s[i] == '0') st += 1 << i;
                x += b << i;
            }
            for (int msk = st; msk >= 0; msk = ((msk - 1) & st)) {
                int v = x | msk;
                int cnt = __builtin_popcount(msk);
                if (cnt & 1) {
                    ans -= dp2[0][v];
                } else {
                    ans += dp2[0][v];
                }
                if (msk == 0) break;
            }
        }
        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