Submission #1127068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127068		Mike_Vu	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1433 ms	21560 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define BITJ(x, j) (((x)>>(j))&1)
#define MASK(j) (1LL<<(j))

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 20;
int n;
int dp1[MASK(maxn)], dp2[MASK(maxn)], val[MASK(maxn)];
string s;
int ans;

void zeta() {
    for (int j = 0; j < n; j++) {
        for (int mask = 0; mask < MASK(n); mask++) {
            if (BITJ(mask, j)) {
                dp1[mask] += dp1[mask^MASK(j)];
            }
        }
        for (int mask = MASK(n)-1; mask >= 0; mask--) {
            if (!BITJ(mask, j)) {
                dp2[mask] += dp2[mask^MASK(j)];
            }
        }
    }
//    for (int mask = 0; mask < MASK(n); mask++) {
//        cout << bitset<3>(mask) << ' ' << dp1[mask] << "\n";
//    }
}

void sinh0(int j, int mask, int cnt) {
    if (j >= n) {
        if (cnt&1) ans -= dp2[mask];
        else ans += dp2[mask];
        return;
    }
    if (s[j] == '0') {
        sinh0(j+1, mask^MASK(n-j-1), cnt+1);
        sinh0(j+1, mask, cnt);
    }
    else if (s[j] == '1') {
        sinh0(j+1, mask^MASK(n-j-1), cnt);
    }
    else {
        sinh0(j+1, mask, cnt);
    }
}
void solvecase0() {
    sinh0(0, 0, 0);
}

void sinh1(int j, int mask, int cnt) {
    if (j >= n) {
//        cout << (bitset<3>)mask << ' ' << cnt << "\n";
        if (cnt&1) ans -= dp1[mask];
        else ans += dp1[mask];
        return;
    }
    if (s[j] == '0') {
        sinh1(j+1, mask, cnt);
    }
    else if (s[j] == '1') {
        sinh1(j+1, mask^MASK(n-j-1), cnt);
        sinh1(j+1, mask, cnt+1);
    }
    else {
        sinh1(j+1, mask^MASK(n-j-1), cnt);
    }
}
void solvecase1() {
    sinh1(0, 0, 0);
}

void sinhbruh(int j, int mask) {
    if (j >= n) {
        ans += val[mask];
        return;
    }
    if (s[j] == '0') {
        sinhbruh(j+1, mask);
    }
    else if (s[j] == '1') {
        sinhbruh(j+1, mask^MASK(n-j-1));
    }
    else {
        sinhbruh(j+1, mask^MASK(n-j-1));
        sinhbruh(j+1, mask);
    }
}
void solvecasebruh() {
    sinhbruh(0, 0);
}

void solvequ(string s) {
    int cnt0, cnt1, cntc;
    cnt0 = cnt1 = cntc = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') cnt0++;
        else if (s[i] == '1') cnt1++;
        else cntc++;
    }
    int temp = min({cnt0, cnt1, cntc});
    ans = 0;
    if (temp == cnt0) return solvecase0();
    else if (temp == cnt1) return solvecase1();
    else return solvecasebruh();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int q;
    cin >> n >> q;
    for (int i = 0; i < MASK(n); i++) {
        char x;
        cin >> x;
        val[i] = x-'0';
        dp1[i] = dp2[i] = val[i];
    }
    zeta();
    cin.ignore();
    while (q--) {
//        cin.ignore();
        getline(cin, s);
//        cin.ignore();
//        cout << s << "\n";
        solvequ(s);
        cout << ans << "\n";
    }
}
/*
3 1
12345678
0??

3 2
12345678
000
0??

3 5
12345678
000
0??
1?0
?11
???
*/

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