Submission #702386

#	Time	Username	Problem	Language	Result	Execution time	Memory
702386		bebra	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	2078 ms	23816 KiB

snake_escaping

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

#define dbg(x) cerr << #x << ": " << x << endl;


constexpr int MAX_Q = 1e6 + 5;
constexpr int MAX_BIT = 20;
constexpr int MAX_N = 1 << 20;
constexpr int MAGIC = 6;

int ans[MAX_Q];
int dp[MAX_N];

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

    int k, q;
    cin >> k >> q;

    string s;
    cin >> s;

    map<int, vector<pair<int, int>>> shifts;
    for (int j = 0; j < q; ++j) {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());

        int mask = 0;
        int shift = 0;
        for (int i = 0; i < k; ++i) {
            if (t[i] == '?') {
                mask |= 1 << i;
            } else if (t[i] == '1') {
                shift |= 1 << i;
            }
        }
        shifts[shift].emplace_back(mask, j);
    }

    for (const auto& [shift, values] : shifts) {
        if (values.size() >= MAGIC) {
            int total_mask = ((1 << k) - 1) & (~shift);

            dp[0] = s[shift] - '0';
            for (int mask = total_mask; mask > 0; mask = (mask - 1) & total_mask) {
                dp[mask] = s[mask | shift] - '0';
            }

            for (int bit = 0; bit < k; ++bit) {
                if (shift & (1 << bit)) continue;
                for (int mask = total_mask; mask > 0; mask = (mask - 1) & total_mask) {
                    if (mask & (1 << bit)) {
                        dp[mask] += dp[mask ^ (1 << bit)];
                    }
                }
            }

            for (const auto& [mask, idx] : values) {
                ans[idx] = dp[mask];
            }

            for (int mask = total_mask; mask > 0; mask = (mask - 1) & total_mask) {
                dp[mask] = 0;
            }

        } else {
            for (const auto& [mask, idx] : values) {
                ans[idx] = s[shift] - '0';
                for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                    ans[idx] += s[submask | shift] - '0';
                }
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}


/*
4
1
3141592653589793
?01?


*/

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