Submission #1163996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163996		MrBrionix	Snake Escaping (JOI18_snake_escaping)	C++20	75 / 100	2093 ms	23184 KiB

snake_escaping

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,popcnt")

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

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

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

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

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

    ll n, q; cin >> n >> q;
    string s; cin >> s;
    vector<ll> a(1 << n, 0);
    for (ll i = 0; i < (1 << n); i++) a[i] = (ll)s[i] - '0';

    vector<ll> pc(1 << n, 0);
    for (ll i = 0; i < (1 << n); i++) pc[i] = __builtin_popcount(i) % 2;

    vector<ll> sos1 = a;

    /* for (ll mk = 0; mk < (1 << n); mk++) cout << sos1[mk] << ' ';
    cout << nl; */

    vector<ll> sos0 = a;
    reverse(sos0.begin(), sos0.end());
    for (ll i = 0; i < n; i++) {
        for (ll mk = 0; mk < (1 << n); mk++) {
            if (mk >> i & 1) {
                sos1[mk] += sos1[mk ^ (1 << i)];
                sos0[mk] += sos0[mk ^ (1 << i)];
            }
        }
    }

    /* for (ll mk = 0; mk < (1 << n); mk++) cout << sos0[mk] << ' ';
    cout << nl; */

    while (q--) {
        string t; cin >> t;
        reverse(t.begin(), t.end());
        ll c0 = 0, c1 = 0, cq = 0;
        ll m0 = 0, m1 = 0, mq = 0;
        for (ll i = 0; i < n; i++) {
            if (t[i] == '0') c0++, m0 += (1 << i);
            else if (t[i] == '1') c1++, m1 += (1 << i);
            else cq++, mq += (1 << i);
        }

        // cout << "solve" << nl;
        if (mq <= 6) {
            ll ans = 0;
            for (ll smq = mq;; smq = (smq - 1) & mq) {
                // cout << m1 + smq << nf;
                ans += a[m1 + smq];
                if (smq == 0) break;
            }
            cout << ans << nl;
        } else if (m1 <= 6) {
            ll ans = 0;
            for (ll sm1 = m1;; sm1 = (sm1 - 1) & m1) {
                ll sgn = pc[m1 ^ sm1];
                // cout << "mk, sgn, sos =" _ mq + sm1 _ sgn _ sos1[mq + sm1] << nl;
                if(!sgn)
                ans += sos1[mq + sm1];
                else
                ans -= sos1[mq + sm1];
                if (sm1 == 0) break;
            }
            cout << ans << nl;
        } else {
            ll ans = 0;
            for (ll sm0 = m0;; sm0 = (sm0 - 1) & m0) {
                ll sgn = pc[m0 ^ sm0];
                
                if(!sgn)
                ans += sos0[mq + sm0];
                else
                ans -= sos0[mq + sm0];
                if (sm0 == 0) break;
            }
            cout << ans << nl;
        }
    }

    return 0;
}

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