Submission #934410

#	Time	Username	Problem	Language	Result	Execution time	Memory
934410		MinaRagy06	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	799 ms	65536 KiB

snake_escaping

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


int dp[21][1 << 20], dp2[21][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;
    int a[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][i] = a[i], dp2[m][i] = a[i];
    for (int i = m - 1; i >= 0; i--) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = dp[i + 1][j];
            dp2[i][j] = dp2[i + 1][j];
            if ((j >> i) & 1) {
                dp[i][j] += dp[i + 1][j ^ (1 << i)];
            } else {
                dp2[i][j] += dp2[i + 1][j ^ (1 << i)];
            }
        }
    }
    while (q--) {
        string s;
        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]) {
            for (int msk = 0; msk < (1 << frq[1]); msk++) {
                int cur = 0, v = 0;
                for (int i = 0; i < m; i++) {
                    int b = s[i] - '0';
                    if (s[i] == '?') b = 1;
                    if (s[i] == '1') b = ((msk >> (cur++)) & 1);
                    v += b << i;
                }
                int cnt = __builtin_popcount(msk);
                if ((frq[1] - cnt) & 1) {
                    ans -= dp[0][v];
                } else {
                    ans += dp[0][v];
                }
            }
        } else {
            for (int msk = 0; msk < (1 << frq[0]); msk++) {
                int cur = 0, v = 0;
                for (int i = 0; i < m; i++) {
                    int b = s[i] - '0';
                    if (s[i] == '?') b = 0;
                    if (s[i] == '0') b = ((msk >> (cur++)) & 1);
                    v += b << i;
                }
                int cnt = __builtin_popcount(msk);
                if (cnt & 1) {
                    ans -= dp2[0][v];
                } else {
                    ans += dp2[0][v];
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

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