Submission #1259167

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259167		nlsosad	Snake Escaping (JOI18_snake_escaping)	C++20	0 / 100	1 ms	328 KiB

snake_escaping

#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[(1<<20)];
int f[(1<<20)], g[(1<<20)];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int l, q;
    if(!(cin >> l >> q)) return 0;
    string s;
    cin >> s;
    int maxn = (1<<l);
    for (int i = 0;i<maxn;++i){
        a[i] = s[i]-'0';
        f[i] = a[i];
        g[i] = a[i];
    }

    // SOS for subsets -> f[mask] = sum_{submask of mask} a[submask]
    for (int i = 0;i<l;++i){
        for (int j = 0;j<maxn;++j){
            if(j & (1<<i)) f[j] += f[j ^ (1<<i)];
            else g[j] += g[j | (1<<i)]; // g[mask] = sum_{superset of mask} a[superset]
        }
    }

    while(q--){
        string t;
        cin >> t;
        reverse(t.begin(), t.end()); // same as original

        int A = 0, B = 0, C = 0;
        for (int i = 0;i<l;++i){
            if(t[i]=='0') A |= (1<<i);
            else if(t[i]=='1') B |= (1<<i);
            else C |= (1<<i);
        }

        // pick smallest among A,B,C (by popcount) to enumerate
        int pcA = __builtin_popcountll(A);
        int pcB = __builtin_popcountll(B);
        int pcC = __builtin_popcountll(C);

        int res = 0;
        if(pcC <= pcA && pcC <= pcB){
            // enumerate submasks of C directly
            int mask = C;
            while(mask > 0){
                res += a[B | mask];
                mask = (mask - 1) & C;
            }
            res += a[B]; // mask = 0
        } else if(pcA <= pcB && pcA <= pcC){
            // inclusion-exclusion over A using g (superset sums)
            int mask = A;
            while(mask > 0){
                if(__builtin_popcountll(mask) % 2 == 0) res += g[B | mask];
                else res -= g[B | mask];
                mask = (mask - 1) & A;
            }
            res += g[B]; // mask = 0
        } else {
            // inclusion-exclusion over B using f (subset sums)
            // NOTE: signs fixed so that for B=0 we get +f[C]
            int mask = B;
            while(mask > 0){
                if(__builtin_popcountll(mask) % 2 == 0) res += f[C | mask];
                else res -= f[C | mask];
                mask = (mask - 1) & B;
            }
            res += f[C]; // mask = 0
        }

        cout << res << '\n';
    }
    return 0;
}

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