Submission #446257

#	Time	Username	Problem	Language	Result	Execution time	Memory
446257		TheScrasse	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1918 ms	29796 KiB

snake_escaping

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

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 1048586

ll i, i1, j, k, k1, tc, n, m, res, flag[10], a, b;
ll dp[2][maxn], cn[3], l, q, mk, ma;
string s, t;

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

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    cin >> l >> q >> s;

    for (mk = 0; mk < (1 << l); mk++) {
        dp[0][mk] = (ll)s[mk] - '0';
        dp[1][mk] = (ll)s[mk ^ ((1 << l) - 1)] - '0';
    }

    for (i = 0; i < l; i++) {
        for (mk = 0; mk < (1 << l); mk++) {
            if ((mk >> i) & 1) {
                dp[0][mk] += dp[0][mk ^ (1 << i)];
                dp[1][mk] += dp[1][mk ^ (1 << i)];
            }
        }
    }

    /* for (mk = 0; mk < (1 << l); mk++) {
        cout << mk _ dp[0][mk] _ dp[1][mk] << nl;
    } */

    while (q--) {
        cin >> t; cn[0] = 0; cn[1] = 0; cn[2] = 0; res = 0;
        k = 0; m = 0;
        reverse(t.begin(), t.end());
        for (i = 0; i < l; i++) {
            if (t[i] == '0') cn[0]++;
            else if (t[i] == '1') cn[1]++;
            else cn[2]++;
        }

        if (cn[0] <= 6) {
            // cout << "t = " << t << nl;
            for (i = 0; i < l; i++) {
                if (t[i] == '?') k += (1 << i);
                else if (t[i] == '0') m += (1 << i);
            }

            for (ma = m;; ma = (ma - 1) & m) {
                // cout << "k, ma = " << k _ ma _ k + ma << nl;
                res += (dp[1][k + ma] * (1 - 2 * (__builtin_popcount(m ^ ma) % 2)));
                if (ma == 0) break;
            }
        } else if (cn[1] <= 6) {
            for (i = 0; i < l; i++) {
                if (t[i] == '?') k += (1 << i);
                else if (t[i] == '1') m += (1 << i);
            }

            for (ma = m;; ma = (ma - 1) & m) {
                res += (dp[0][k + ma] * (1 - 2 * (__builtin_popcount(m ^ ma) % 2)));
                if (ma == 0) break;
            }
        } else {
            for (i = 0; i < l; i++) {
                if (t[i] == '1') k += (1 << i);
                else if (t[i] == '?') m += (1 << i);
            }

            for (ma = m;; ma = (ma - 1) & m) {
                res += (ll)s[k + ma] - '0';
                if (ma == 0) break;
            }
        }

        cout << res << nl;
    }

    return 0;
}

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