Submission #1111982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111982		_8_8_	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1888 ms	42312 KiB

snake_escaping

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
    
const int  N = (1 << 20) + 12, MOD = (int)1e9 + 7;

int l, q, a[N], dp[N], pd[N];
void test() {
    cin >> l >> q;
    for(int i = 0; i < (1 << l); i++) {
        char x;
        cin >> x;
        a[i] = (x - '0');
        dp[i] = pd[i] = a[i];
    }
    for(int i = 0; i < l; i++) {
        for(int j = 0; j < (1 << l); j++) {
            if((j >> i) & 1) {
                dp[j] += (dp[j - (1 << i)]);
            }
        }
        for(int j = (1 << l) - 1; j >= 0; j--) {
            if(!((j >> i) & 1)) {
                pd[j] += pd[j + (1 << i)];
            }
        }
    }
    while(q--) {
        vector<int> d, e, f;
        int s = 0;
        for(int i = l - 1; i >= 0; i--) {
            char x;
            cin >> x;
            if(x == '0') {
                d.push_back(i);
            } else if(x == '1') {
                s += (1 << i);
                e.push_back(i);
            } else {
                f.push_back(i);
            }
        }
        int res = 0, m;
        if((int)f.size() <= 7 ) {
            m = (int)f.size();
            for(int i = 0; i < (1 << m); i++) {
                int v = s;
                for(int j = 0; j < m; j++) {
                    if((i >> j) & 1) {
                        v += (1 << f[j]);
                    }
                }
                res += a[v];
            }
        } else if((int)e.size() <= 7) {
            m = (int)e.size();
            for(int i:f) {
                s += (1 << i);
            }
            res = 0;

            for(int i = 0; i < (1 << m); i++) {
                int v = s;
                for(int j = 0; j < m; j++) {
                    if((i >> j) & 1) {
                        v -= (1 << e[j]);
                    }
                }
                if(__builtin_popcount(i) & 1) {
                    res -= dp[v];
                } else {
                    res += dp[v];
                }
            }
        } else {
            m = (int)d.size();
            for(int i = 0; i < (1 << m); i++) {
                int v = s;
                for(int j = 0; j < m; j++) {
                    if((i >> j) & 1) {
                        v += (1 << d[j]);
                    }
                }
                if(__builtin_popcount(i) & 1) {
                    res -= pd[v];
                } else {
                    res += pd[v];
                }
            }
        }

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

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

    int t = 1; 
    // cin >> t;

    while(t--) 
        test();
}

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