Submission #522337

#	Time	Username	Problem	Language	Result	Execution time	Memory
522337		Monarchuwu	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2004 ms	21816 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 (m2 <= l / 3) { // brute ?
            for (int m = m2; true; m = (m - 1) & m2) {
                ans += a[m | m1];
                if (m == 0) break;
            }
        }
        else if (m0 == l / 3) { // inc-exc 0, dp sos 1 and ? => dùng g
            for (int m = m0; true; m = (m - 1) & m0) {
                if (lg[m] & 1)
                    ans -= g[m | m1];
                else ans += g[m | m1];
                if (m == 0) break;
            }
        }
        else { // inc-exc 1, dp sos 0 and ? => dùng f
            for (int m = m1, k = lg[m1] & 1; true; m = (m - 1) & m1) {
                if ((lg[m] & 1) == k)
                    ans += f[m | m2];
                else ans -= f[m | m2];
                if (m == 0) break;
            }
        }
        cout << ans << '\n';
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

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