Submission #941296

#	Time	Username	Problem	Language	Result	Execution time	Memory
941296		Amirreza_Fakhri	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	528 ms	38908 KiB

snake_escaping

// In the name of the God
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define pb push_back
#define F first
#define S second
#define mp make_pair
#define pii pair <int, int>
#define smin(x, y) (x) = min((x), (y))
#define smax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(), (x).end()
using namespace std;

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")

const int inf = 1e9+7;
const int mod = 998244353;
const int maxn = 20;

int l, q, dp1[1<<maxn], dp2[1<<maxn];
string s, t;

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> l >> q >> s;
    for (int i = 0; i < (1<<l); i++) dp1[i] = dp2[(1<<l)-i-1] = s[i]-'0';
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < (1<<l); j++) {
            if (j&(1<<i)) dp1[j] += dp1[j^(1<<i)], dp2[j] += dp2[j^(1<<i)];
        }
    }
    while (q--) {
        int cnt0 = 0, cnt1 = 0, cnt2 = 0, m1 = 0, m2 = 0, ans = 0;
        cin >> t;
        reverse(all(t));
        for (int i = 0; i < l; i++) {
            if (t[i] == '0') cnt0++;
            else if (t[i] == '1') cnt1++;
            else cnt2++;
        }
        // cout << cnt0 << ' ' << cnt1 << ' ' << cnt2 << '\n';
        if (cnt0 <= min(cnt1, cnt2)) {
            // cout << "HI1\n";
            for (int i = 0; i < l; i++) {
                if (t[i] == '0') m1 |= (1<<i);
                else if (t[i] == '?') m2 |= (1<<i);
            }
            for (int sm = m1; sm; sm = (sm-1)&m1) {
                if (__builtin_parity(m1^sm)) ans -= dp2[sm^m2];
                else ans += dp2[sm^m2];
            }
            if (__builtin_parity(m1)) ans -= dp2[m2];
            else ans += dp2[m2];
            cout << ans << '\n';
        }
        else if (cnt1 <= min(cnt0, cnt2)) {
            // cout << "HI2\n";
            for (int i = 0; i < l; i++) {
                if (t[i] == '1') m1 |= (1<<i);
                else if (t[i] == '?') m2 |= (1<<i);
            }
            for (int sm = m1; sm; sm = (sm-1)&m1) {
                if (__builtin_parity(m1^sm)) ans -= dp1[sm^m2];
                else ans += dp1[sm^m2];
            }
            if (__builtin_parity(m1)) ans -= dp1[m2];
            else ans += dp1[m2];
            cout << ans << '\n';
        }
        else {
            // cout << "HI3\n";
            for (int i = 0; i < l; i++) {
                if (t[i] == '?') m1 |= (1<<i);
                else if (t[i] == '1') m2 |= (1<<i);
            }
            for (int sm = m1; sm; sm = (sm-1)&m1) ans += s[sm^m2]-'0';
            ans += s[m2]-'0';
            cout << ans << '\n';
        }
    }
    return 0;
}

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