Submission #1306088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306088		thecrazycandy	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1127 ms	32888 KiB

snake_escaping

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
#define ll long long
#define sped_up ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define S second
#define F first
const ll INF = (ll)1e9 + 1, INFL = (ll)1e18 + 1;
const ll mod = (ll)1e9 + 7, MAXN = (ll)(1 << 20);
ll dp[2][MAXN];
ll a[MAXN];
int main() {
    sped_up;
    ll n, q;
    cin >> n >> q;
    for (int i = 0; i < (1 << n); i++) {
        char c;
        cin >> c;
        a[i] = c - '0';
        dp[0][i] += c - '0';
        dp[1][i] += c - '0';
    }
    for (int i = 0; i < n; i++) {
        for (int mask = 0; mask < (1 << n); mask++) {
            if ((mask >> i) & 1) dp[1][mask] += dp[1][mask ^ (1 << i)];
            if (!((mask >> i) & 1)) dp[0][mask] += dp[0][mask ^ (1 << i)];
        }
    }
    while (q--) {
        vector <ll> v0, v1, v;
        ll f = 0, s = 0, ans = 0; 
        ll cnt0 = 0, cnt1 = 0, cnt = 0;
        for (int i = n - 1; i >= 0; i--) {
            char c;
            cin >> c;
            if (c == '1') f |= (1 << i), s |= (1 << i), cnt1++, v1.pb(i);
            else if (c == '?') f |= (1 << i), cnt++, v.pb(i);
            else cnt0++, v0.pb(i);
        }
        if (cnt1 <= 6) {
            for (int mask = 0; mask < (1 << cnt1); mask++) {
                ll nw = f;
                for (int i = 0; i < cnt1; i++) {
                    if ((mask >> i) & 1) nw ^= (1 << v1[i]);
                }
                if (__builtin_popcount(mask) % 2 == 0) ans += dp[1][nw];
                else ans -= dp[1][nw];
            }
        }
        else if (cnt0 <= 6) {
            for (int mask = 0; mask < (1 << cnt0); mask++) {
                ll nw = s;
                for (int i = 0; i < cnt0; i++) {
                    if ((mask >> i) & 1) nw ^= (1 << v0[i]);
                }
                if (__builtin_popcount(mask) % 2 == 0) ans += dp[0][nw];
                else ans -= dp[0][nw];
            }
        }
        else {
            for (int mask = 0; mask < (1 << cnt); mask++) {
                ll nw = f;
                for (int i = 0; i < cnt; i++) {
                    if ((mask >> i) & 1) nw ^= (1 << v[i]);
                }
                ans += a[nw];
            }
        }
        cout << ans << '\n';
    }
}

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