Submission #674300

#	Time	Username	Problem	Language	Result	Execution time	Memory
674300		Kahou	Snake Escaping (JOI18_snake_escaping)	C++14	100 / 100	831 ms	42096 KiB

snake_escaping

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int M = (1<<20) + 50, N = 3;
int l, q, f[M], dp[2][M];
int A[3];

void solve() {
        cin >> l >> q;
        for (int mask = 0; mask < (1<<l); mask++) {
                char c;
                cin >> c;
                dp[0][mask] = dp[1][mask] = f[mask] = c-'0';
        }
        for (int i = 0; i < l; i++) {
                for (int mask = 0; mask < (1<<l); mask++) {
                        if (mask>>i&1) dp[0][mask] += dp[0][mask^(1<<i)];
                        else dp[1][mask] += dp[1][mask^(1<<i)];
                }
        }
        while (q--) {
                string t;
                cin >> t;

                A[0] = A[1] = A[2] = 0;
                int ans = 0;
                for (int i = 0; i < l; i++) {
                        int c = (t[i] != '0') + (t[i] == '?');
                        A[c] ^= 1<<(l-i-1);
                }
                int m = 0;
                if (__builtin_popcount(A[1]) < __builtin_popcount(A[m])) m = 1;
                if (__builtin_popcount(A[2]) < __builtin_popcount(A[m])) m = 2;
                if (m == 0) {
                        ans = dp[1][A[1]];
                        for (int mask = A[0]; mask > 0; mask = (mask-1)&A[0]) {
                                ans += (__builtin_popcount(mask)&1? -1:1)*dp[1][mask^A[1]];
                        }
                }
                else if (m == 1) {
                        ans = (__builtin_popcount(A[1])&1? -1:1)* dp[0][A[2]];
                        for (int mask = A[1]; mask > 0; mask = (mask-1)&A[1]) {
                                ans += (__builtin_popcount(mask^A[1])&1? -1:1)* dp[0][mask^A[2]];
                        }
                }
                else {
                        ans = f[A[1]];
                        for (int mask = A[2]; mask > 0; mask = (mask-1)&A[2]) {
                                ans += f[mask^A[1]];
                        }
                }
                cout << ans << endl;
        }
}
int main() {
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        solve();
        return 0;
}

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