Submission #1099118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099118		LOLOLO	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	616 ms	43228 KiB

snake_escaping

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

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1 << 20;
int f1[N], f2[N], v[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;

    string s;
    cin >> s;

    int all = (1 << n) - 1;
    for (int i = 0; i < (1 << n); i++) {
        v[i] = s[i] - '0';
        f1[i] = v[i];
        f2[all ^ i] = v[i];
    }

    for (int i = 0; i < n; i++) {
        for (int mask = (1 << n) - 1; mask >= 0; mask--) {
            if ((mask & (1 << i)))
                continue;

            f1[mask] += f1[mask ^ (1 << i)];
            f2[mask] += f2[mask ^ (1 << i)];
        }
    }

    for (int i = 0; i < q; i++) {
        string s;
        cin >> s;
        int on = 0, off = 0, cc = 0;

        for (int j = 0; j < n; j++) {
            if (s[j] == '1') {
                on |= (1 << (n - j - 1));
            }

            if (s[j] == '0') {
                off |= (1 << (n - j - 1));
            }

            if (s[j] == '?') {
                cc |= (1 << (n - j - 1));
            }
        }

        int ans = 0;
        if (cntbit(cc) <= 6) {
            ans = v[on];
            for (int sub = cc; sub; sub = cc & (sub - 1)) {
                ans += v[sub | on];
            }
        } else if (cntbit(on) <= 6) {
            ans = f2[off];
            for (int sub = on; sub; sub = on & (sub - 1)) {
                if (cntbit(sub) % 2) {
                    ans -= f2[sub | off];
                } else {
                    ans += f2[sub | off];
                }
            }
        } else {
            ans = f1[on];
            for (int sub = off; sub; sub = off & (sub - 1)) {
                if (cntbit(sub) % 2) {
                    ans -= f1[sub | on];
                } else {
                    ans += f1[sub | on];
                }
            }
        }

        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