제출 #1295653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1295653		fairkrash	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2062 ms	18252 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
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 <= 10) {
            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 << 30) - 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;
    }
}

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