Submission #897364

#	Time	Username	Problem	Language	Result	Execution time	Memory
897364		box	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	490 ms	43484 KiB

snake_escaping

#include <bits/stdc++.h>
using namespace std;
    
const int L = 20, N = 1 << L;
    
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int l, q; cin >> l >> q;
    string s; cin >> s;
    int n = 1 << l;
    static int f[N], g[N], c[N];
    for (int i = 0; i < n; i++)
        f[i] += s[i] - '0', g[i] += s[i] - '0';
    for (int i = 1; i < n; i++)
        c[i] = c[i & (i - 1)] + 1;
    for (int b = 0; b < l; b++)
        for (int i = 0; i < n; i++)
            if (i >> b & 1) {
                f[i] += f[i ^ (1 << b)];
                g[i ^ (1 << b)] += g[i];
            }
    while (q--) {
        string t; cin >> t;
        reverse(t.begin(), t.end());
        int i0 = 0, i1 = 0, iq = 0;
        for (int b = 0; b < l; b++)
            if (t[b] == '0') i0 |= 1 << b;
            else if (t[b] == '1') i1 |= 1 << b;
            else iq |= 1 << b;
        int v = 0;
        if (c[iq] <= 7) {
            for (int t = iq; ; t = (t - 1) & iq) {
                v += s[t | i1] - '0';
                if (t == 0) break;
            }
        } else if (c[i0] <= 7) {
            for (int t = i0; ; t = (t - 1) & i0) {
                v += (c[t] % 2 ? -1 : +1) * g[t | i1];
                if (t == 0) break;
            }
        } else {
            for (int t = i1; ; t = (t - 1) & i1) {
                v += (c[t] % 2 ? -1 : +1) * f[(t ^ i1) | iq];
                if (t == 0) break;
            }
        }
        cout << v << '\n';
    }
    return 0;
}

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