제출 #702376

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702376		bebra	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	2076 ms	24148 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 = 10;

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;
        int bits_cnt = 0;
        for (int i = 0; i < k; ++i) {
            if (t[i] == '?') {
                mask |= 1 << i;
                ++bits_cnt;
            } else if (t[i] == '1') {
                shift |= 1 << i;
            }
        }

        if (bits_cnt < MAGIC) {
            int res = s[shift] - '0';
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                res += s[submask + shift] - '0';
            }
            ans[j] = res;
        } else {
            shifts[shift].emplace_back(mask, j);
        }
    }

    int n = 1 << k;
    for (auto [shift, values] : shifts) {
        memset(dp, 0, sizeof(dp));

        for (int mask = 0; (mask | shift) < n; ++mask) {
            if ((mask & shift) == 0) {
                dp[mask] = s[mask | shift] - '0';
            }
        }

        for (int bit = 0; bit < k; ++bit) {
            if (shift & (1 << bit)) continue;

            for (int mask = 0; mask < n; ++mask) {
                if ((mask & shift) != 0) continue;

                if (mask & (1 << bit)) {
                    dp[mask] += dp[mask ^ (1 << bit)];
                }
            }
        }

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

    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