Submission #522354

#	Time	Username	Problem	Language	Result	Execution time	Memory
522354		Monarchuwu	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	711 ms	25904 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;

int pw[20 + 1], lg[N];
int a[N], f[N], g[N]; // f chứa con (1 = 01), g chứa cha (0 = 01)
void prep() {
    pw[0] = 1;
    for (int i = 1; i <= l; ++i) pw[i] = pw[i - 1] << 1;

    for (int msk = 0; msk < pw[l]; ++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 < pw[l]; ++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);
        for (char c : t) {
            m0 <<= 1, m1 <<= 1, m2 <<= 1;
            if (c == '0') ++m0;
            else if (c == '1') ++m1;
            else ++m2;
        }

        int ans(0);
        if (lg[m2] <= l / 3) { // brute ?
            ans = a[m1];
            for (int m = m2; m; m = (m - 1) & m2)
                ans += a[m | m1];
        }
        else if (lg[m0] <= l / 3) { // 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] & 1 ? -g[m | m1] : g[m | m1];
        }
        else { // inc-exc 1, dp sos 0 and ? => dùng f
            ans = lg[m1] & 1 ? -f[m2] : f[m2];
            for (int m = m1, k = lg[m1] & 1; m; m = (m - 1) & m1)
                ans += (lg[m] & 1) == k ? 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