Submission #1100371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100371		KietJ	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	647 ms	50764 KiB

snake_escaping

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

#define f first
#define s second
#define pb(x) push_back(x)
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define un(x) (x).erase(unique(all(x)), x.end())

typedef long long ll;
typedef double db;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector <ll> V;

const int N = 1e7 + 1;
const int M = (1 << 20);
const int mod = 1e9 + 7;
const int inf = 1061109567;
const int block = 490;

template <class T1, class Gz> void add(T1 &x, Gz y) { x += y; if (x < 0) x += mod; if (x >= mod) x -= mod; }
template <class T1, class Gz> bool maximize(T1 &x, Gz y) { if (x < y) { x = y; return true; } return false; }
template <class T1, class Gz> bool minimize(T1 &x, Gz y) { if (x > y) { x = y; return true; } return false; }

int n, q, a[M];
ll dp[2][M];

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

    cin >> n >> q;

    for(int i = 0; i < (1 << n); i++) {
        char x; cin >> x;
        a[i] = x - '0';
        for(int j = 0; j < 2; j++)  
            dp[j][i] = a[i];
    }

    for(int i = 0; i < n; i++) {
        for(int mask = 0; mask < (1 << n); mask++) {
            if (mask >> i & 1) {
                dp[0][mask ^ (1 << i)] += dp[0][mask]; 
                dp[1][mask] += dp[1][mask ^ (1 << i)]; 
            }
        }
    }

    for(int i = 1; i <= q; i++) {
        string s; cin >> s;
        reverse(all(s));

        vector <int> mask(3, 0);

        for(int j = 0; j < n; j++) {
            char x = s[j];
            if (x == '0') mask[0] ^= (1 << j);
            if (x == '1') mask[1] ^= (1 << j);
            if (x == '?') mask[2] ^= (1 << j);
        }

        ll ans = 0;
        if (__builtin_popcount(mask[2]) <= 6) {
            ans = a[mask[1]];
            for(int mask1 = mask[2]; mask1; mask1 = (mask1 - 1) & mask[2]) {
                ans += a[mask[1] ^ mask1];
            }
        } else {
            if (__builtin_popcount(mask[0]) <= 6) {
                ans = dp[0][mask[1]];
                for(int mask1 = mask[0]; mask1; mask1 = (mask1 - 1) & mask[0]) {
                    if (__builtin_popcount(mask1) & 1) {
                        ans -= dp[0][mask[1] ^ mask1];
                    } else {
                        ans += dp[0][mask[1] ^ mask1];
                    }
                }
            } else {
                int lim = __builtin_popcount(mask[1]);

                if (lim & 1) {
                    ans -= dp[1][mask[2]];
                } else {
                    ans += dp[1][mask[2]];
                }

                for(int mask1 = mask[1]; mask1; mask1 = (mask1 - 1) & mask[1]) {
                    if ((lim - __builtin_popcount(mask1)) & 1) {
                        ans -= dp[1][mask1 ^ mask[2]];
                    }  else {
                        ans += dp[1][mask1 ^ mask[2]];
                    }
                }
            }
        } 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