Submission #1295655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295655		fairkrash	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1949 ms	13576 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;
using ll = int;
ll INF = 1e18;
ll MOD = 1e9 + 7;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<ll> dp(1 << n);
    for (ll i = 0; i < s.size(); i++) {
        dp[i] += (s[i] - '0');
    }
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < (1 << n); j++) {
            if (((1 << i) & j) != 0) {
                dp[j] += dp[j - (1 << i)];
            }
        }
    }
    for (ll ij = 0; ij < q; ij++) {
        string z;
        cin >> z;
        ll mask1 = 0, mask2 = 0;
        ll bit = n - 1;
        ll col = 0;
        for (ll j = 0; j < z.size(); j++) {
            if (z[j] == '1') {
                mask1 += (1 << bit);
                mask2 += (1 << bit);
            }
            if (z[j] == '?') {
                col++;
                mask2 += (1 << bit);
            }
            bit--;
        }
        if (col <= 12) {
            ll cool = mask2 - (mask2 & mask1);
            ll mask = cool;
            ll ans = 0;
            while (true) {
                ans += s[mask + mask1] - '0';
                if (mask == 0)break;
                mask--;
                mask &= cool;
            }
            cout << ans << endl;
            continue;
        }
        ll ans = 0;
        ll mask = mask1;
        ll u1 = 0;
        {
            ll x1 = mask2;
            while (x1 != 0) {
                x1 -= (x1 & (-x1));
                u1++;
            }
        }
        while (true) {
            ll d = mask2 & (((1 << 23) - 1) - mask);
            ll u = 0;
            ll x1 = d;
            while (x1 != 0) {
                x1 -= (x1 & (-x1));
                u++;
            }
            if (u % 2 == u1 % 2) {
                ans += dp[d];
            } else {
                ans -= dp[d];
            }
            if (mask == 0)break;
            mask--;
            mask &= mask1;
        }
        cout << ans << endl;
    }
}

Compilation message (stderr)

snake_escaping.cpp:5:10: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
    5 | ll INF = 1e18;
      |          ^~~~

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