Submission #522360

#	Time	Username	Problem	Language	Result	Execution time	Memory
522360		Monarchuwu	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	671 ms	22756 KiB

snake_escaping

#include<iostream>
#include<algorithm>
#include<string>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1 << 20;
int l, q;
string s;

bool lg[N];
int a[N], f[N], g[N]; // f chứa con (1 = 01), g chứa cha (0 = 01)
void prep() {
    int MASK(1 << l);
    for (int msk = 0; msk < MASK; ++msk) {
        lg[msk] = lg[msk >> 1] ^ (msk & 1);
        a[msk] = f[msk] = g[msk] = s[msk] ^ 48;
    }

    for (int j = 0; j < l; ++j)
        for (int msk = 0; msk < MASK; ++msk)
            if (msk >> j & 1)
                f[msk] += f[msk ^ (1 << j)];
            else g[msk] += g[msk | (1 << j)];
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> l >> q >> s;
    prep();

    while (q--) {
        string t; cin >> t;
        int m0(0), m1(0), m2(0), cnt0(0), cnt1(0), cnt2(0);
        for (char c : t) {
            m0 <<= 1, m1 <<= 1, m2 <<= 1;
            if (c == '0') ++m0, ++cnt0;
            else if (c == '1') ++m1, ++cnt1;
            else ++m2, ++cnt2;
        }

        int ans(0), mi = min({ cnt0, cnt1, cnt2 });
        if (cnt2 == mi) { // brute ?
            ans = a[m1];
            for (int m = m2; m; m = (m - 1) & m2)
                ans += a[m | m1];
        }
        else if (cnt0 == mi) { // inc-exc 0, dp sos 1 and ? => dùng g
            ans = g[m1];
            for (int m = m0; m; m = (m - 1) & m0)
                ans += lg[m] ? -g[m | m1] : g[m | m1];
        }
        else { // inc-exc 1, dp sos 0 and ? => dùng f
            ans = lg[m1] ? -f[m2] : f[m2];
            for (int m = m1; m; m = (m - 1) & m1)
                ans += lg[m] == lg[m1] ? f[m | m2] : -f[m | m2];
        }
        cout << ans << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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