Submission #1110865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110865		anmattroi	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	557 ms	46408 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

int L, q;
int a[1<<20], Dp_sub[1<<20], Dp_par[1<<20], dem[1<<20];

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



    cin >> L >> q;
    for (int i = 0; i < (1<<L); i++) {
        char c; cin >> c;
        a[i] = Dp_sub[i] = Dp_par[i] = c-'0';
        dem[i] = __builtin_popcount(i);
    }

    for (int i = 0; i < L; i++) {
        for (int mask = 0; mask < (1<<L); ++mask) {
            if ((mask>>i)&1) Dp_sub[mask] += Dp_sub[mask^(1<<i)];
            else Dp_par[mask] += Dp_par[mask^(1<<i)];
        }
    }

    auto sub1 = [&](const string &s) -> void {
        int mask = 0, Smask = 0;
        for (int i = 0; i < L; i++) {
            if (s[i] != '?') mask |= ((s[i]-'0') << i);
            else Smask |= (1<<i);
        }
        int ans = a[mask];
        for (int i = Smask; i > 0; i = (i-1)&Smask) ans += a[i^mask];
        cout << ans << "\n";
    };

    auto sub2 = [&](const string &s) -> void {
        int mask = 0, Smask = 0;
        for (int i = 0; i < L; i++) {
            if (s[i] == '1') {
                Smask |= (1<<i);
                mask |= (1<<i);
            } else if (s[i] == '?') mask |= (1<<i);
        }
        int ans = Dp_sub[mask];

        for (int i = Smask; i > 0; i = (i-1)&Smask) {
            if (dem[i]&1) ans -= Dp_sub[mask^i];
            else ans += Dp_sub[mask^i];
        }
        cout << ans << "\n";
    };

    auto sub3 = [&](const string &s) -> void {
        int mask = 0, Smask = 0;
        for (int i = 0; i < L; i++) {
            if (s[i] == '0') Smask |= (1<<i);
            else if (s[i] == '1') mask |= (1<<i);
        }
        int ans = Dp_par[mask];

        for (int i = Smask; i > 0; i = (i-1)&Smask) {
            if (dem[i]&1) ans -= Dp_par[mask^i];
            else ans += Dp_par[mask^i];
        }
        cout << ans << "\n";
    };

    while (q--) {
        string s; cin >> s;
        reverse(s.begin(), s.end());
        int cnt0 = 0, cnt1 = 0, cnt2 = 0;
        for (char ch : s) {
            switch (ch) {
                case '0' :
                    ++cnt0;
                    break;
                case '1' :
                    ++cnt1;
                    break;
                case '?' :
                    ++cnt2;
                    break;
                }
        }
        if (cnt2 <= 6) sub1(s);
        else if (cnt1 <= 6) sub2(s);
        else sub3(s);
    }
}

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