Submission #1194622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194622		LucaIlie	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1039 ms	21952 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 20;
int cost[1 << MAX_N], sumDown[1 << MAX_N], sumUp[1 << MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    string c;
    cin >> n >> q;
    cin >> c;

    for (int mask = 0; mask < (1 << n); mask++)
        cost[mask] = sumDown[mask] = sumUp[mask] = c[mask] - '0';

    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if ((mask >> i) & 1)
                sumDown[mask] += sumDown[mask ^ (1 << i)];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int mask = (1 << n) - 1; mask >= 0; mask--) {
            if (!((mask >> i) & 1))
                sumUp[mask] += sumUp[mask ^ (1 << i)];
        }
    }

    while (q--) {
        string s;
        cin >> s;
        reverse(s.begin(), s.end());

        vector<int> pq, p0, p1;
        for (int i = 0; i < n; i++) {
            if (s[i] == '?')
                pq.push_back(i);
            else if (s[i] == '0')
                p0.push_back(i);
            else
                p1.push_back(i);
        }

        int ans = 0;
        if ((int)p0.size() <= 6) {
            int mask = 0;
            for (int i = 0; i < n; i++)
                mask += ((s[i] == '1') << i);

            for (int fixed = 0; fixed < (1 << p0.size()); fixed++) {
                int newMask = mask, cnt = 0;
                for (int i = 0; i < (int)p0.size(); i++) {
                    if ((fixed >> i) & 1) {
                        cnt++;
                        newMask += (1 << p0[i]);
                    }
                }
                if (cnt % 2 == 0)
                    ans += sumUp[newMask];
                else
                    ans -= sumUp[newMask];
            }
        } else if ((int)p1.size() <= 6) {
            int mask = 0;
            for (int i = 0; i < n; i++)
                mask += ((s[i] != '0') << i);

            for (int fixed = 0; fixed < (1 << p1.size()); fixed++) {
                int newMask = mask, cnt = 0;
                for (int i = 0; i < (int)p1.size(); i++) {
                    if ((fixed >> i) & 1) {
                        cnt++;
                        newMask -= (1 << p1[i]);
                    }
                }
                if (cnt % 2 == 0)
                    ans += sumDown[newMask];
                else
                    ans -= sumDown[newMask];
            }
        } else {
            int mask = 0;
            for (int i = 0; i < n; i++)
                mask += ((s[i] == '1') << i);

            for (int fixed = 0; fixed < (1 << pq.size()); fixed++) {
                int newMask = mask;
                for (int i = 0; i < (int)pq.size(); i++) {
                    if ((fixed >> i) & 1)
                        newMask += (1 << pq[i]);
                }
                ans += cost[newMask];
            }
        }

        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