Submission #557059

#	Time	Username	Problem	Language	Result	Execution time	Memory
557059		Jomnoi	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	812 ms	47408 KiB

snake_escaping

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

const int MAX_L = 20;
const int MAX_N = (1<<MAX_L);

int S[MAX_N];
int super[MAX_N], sub[MAX_N];
int cnt_bit[MAX_N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int L, Q;
    string str;
    cin >> L >> Q >> str;
    for(int i = 0; i < (1<<L); i++) {
        S[i] = super[i] = sub[i] = str[i] - '0';
        cnt_bit[i] = __builtin_popcount(i);
    }

    for(int i = 0; i < L; i++) {
        for(int mask = 0; mask < (1<<L); mask++) {
            if(mask & (1<<i)) {
                sub[mask] += sub[mask ^ (1<<i)];
            }
            else {
                super[mask] += super[mask ^ (1<<i)];
            }
        }
    }

    while(Q--) {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());

        int A = 0, B = 0, C = 0;
        int cntA = 0, cntB = 0, cntC = 0;
        for(int i = 0; i < L; i++) {
            if(t[i] == '0') {
                A |= (1<<i);
                cntA++;
            }
            else if(t[i] == '1') {
                B |= (1<<i);
                cntB++;
            }
            else { // t[i] == '?'
                C |= (1<<i);
                cntC++;
            }
        }

        int ans = 0;
        if(cntA <= min(cntB, cntC)) {
            for(int mask = A;; mask = (mask - 1) & A) {
                if(cnt_bit[mask] % 2 == 0) {
                    ans += super[B | mask];
                }
                else {
                    ans -= super[B | mask];
                }

                if(mask == 0) {
                    break;
                }
            }
        }
        else if(cntB <= min(cntA, cntC)) {
            for(int mask = B;; mask = (mask - 1) & B) {
                if(cnt_bit[mask] % 2 == 0) {
                    ans += sub[C | (mask ^ B)];
                }
                else {
                    ans -= sub[C | (mask ^ B)];
                }

                if(mask == 0) {
                    break;
                }
            }
        }
        else if(cntC <= min(cntA, cntB)) {
            for(int mask = C;; mask = (mask - 1) & C) {
                ans += S[mask | B];

                if(mask == 0) {
                    break;
                }
            }
        }

        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