Submission #1302123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302123		ChottuF	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	1881 ms	22000 KiB

snake_escaping

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

int main(){
    int L, Q;
    cin >> L >> Q;
    vector<int> arr(1<<L);
    vector<int> sub(1<<L), sup(1<<L);
    string s;
    cin >> s;
    for (int i = 0; i<(1<<L); i++){
        arr[i] = s[i] - '0';
        sub[i] = arr[i];
        sup[i] = arr[i];
    }
    
    for (int i = 0; i<L; i++){
        for (int j = 0; j<(1<<L); j++){
            if (j & (1 << i)){
                sub[j] += sub[j ^ (1 << i)];
            }
        }
    }
    
    
    for (int i = 0; i<L; i++){
        for (int j = 0; j<(1<<L); j++){
            if (j & (1 << i)){
                sup[j ^ (1 << i)] += sup[j];
            }
        }
    }
    
    while (Q--){
        string t;
        cin >> t;
        reverse(t.begin(),t.end());
        int one = 0;
        int zero = 0;
        int question = 0;
        for (int i = 0; i<L; i++){
            if (t[i] == '0') zero++;
            else if (t[i] == '1') one++;
            else question++;
        }
        
        if (question <= 6){
            int msk = 0;
            vector<int> idx;
            for (int i = 0; i<L; i++){
                if (t[i] == '?'){
                    idx.push_back(i);
                }
                else if (t[i] == '1'){
                    msk |= 1 << i;
                }
            }
            int sz = idx.size();
            int ans = 0;
            for (int i = 0; i<(1<<sz); i++){
                //distribute across indices
                int cr = msk;
                for (int j = 0; j<sz; j++){
                    if (i & (1 << j)){
                        cr += 1<<idx[j];
                    }
                }
                ans += arr[cr];
            }
            cout << ans << '\n';
        }
        else if (one <= 6){
            int msk = 0;
            int flp = 0;
            for (int i = 0; i<L; i++){
                if (t[i] == '1'){
                    msk |= 1 << i;
                    flp |= 1 << i;
                }
                else if (t[i] == '?'){
                    msk |= 1 << i;
                }
            }
            int ans = 0;
            for (int s = flp; s >= 0; s = (s-1) & flp){
                int idx = s ^ msk;
                int nm = __builtin_popcount(s);
                if (nm%2 == 0){
                    ans += sub[idx];
                }
                else{
                    ans -= sub[idx];
                }
                if (s == 0) break;
            }
            cout << ans << '\n';
        }
        else{
            int msk = 0;
            int ans = 0;
            int flp = 0;
            for (int i = 0; i<L; i++){
                if (t[i] == '0'){
                    flp |= 1 << i;
                }
                else if (t[i] == '1'){
                    msk |= 1 << i;
                }
            }
            for (int s = flp; s>=0; s = (s-1) & flp){
                int idx = s ^ msk;
                int nm = __builtin_popcount(s);
                if (nm%2 == 0){
                    ans += sup[idx];
                }
                else{
                    ans -= sup[idx];
                }
                if (s == 0) break;
            }
            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