Submission #1310788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310788		syanvu	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	384 ms	25840 KiB

snake_escaping

// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define pb push_back
#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
// #define int long long
#define all(v) v.begin(),v.end()
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 3e5 + 1, inf = 1e15, mod = 998244353;

void solve(){
    int l, q;
    cin >> l >> q;
    string s;
    cin >> s;
    int n = (1 << l);
    int a[n], dp0[n], dp1[n], t[n];
    for(int i = 0; i < n; i++){
        a[i] = s[i] - '0';
        dp1[i] = a[i];
        dp0[n - i - 1] = a[i]; 
        t[i] = (__builtin_popcount(i) % 2 == 0 ? 1 : -1);
    }
    for(int i = 0; i < l; i++){
        for(int mask = 0; mask < n; mask++){
            if((mask >> i) & 1){
                dp1[mask] += dp1[mask ^ (1 << i)];
                dp0[mask] += dp0[mask ^ (1 << i)];
            }
        }
    }
    while(q--){
        string s;
        cin >> s;
        reverse(all(s));
        int c0 = 0, c1 = 0, cs = 0;
        int m0 = 0, m1 = 0, ms = 0;
        for(int i = 0; i < l; i++){
            if(s[i] == '0') c0++, m0 |= (1 << i);
            if(s[i] == '1') c1++, m1 |= (1 << i);
            if(s[i] == '?') cs++, ms |= (1 << i); 
        }
        int ans = 0;
        if(cs <= 6){
            for(int m = ms;; m = (m - 1) & ms){
                ans += a[m | m1];
                if(m <= 0) break;
            }
        }
        else if(c1 <= 6){
            for(int m = m1;; m = (m - 1) & m1){
                ans += dp1[m | ms] * t[m1 ^ m];
                if(m <= 0) break;
            }
        }
        else{
            for(int m = m0;; m = (m - 1) & m0){
                ans += dp0[m | ms] * t[m0 ^ m];
                if(m <= 0) break;
            }
        }
        cout << ans << '\n';
    }
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

snake_escaping.cpp:15:30: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   15 | const int N = 3e5 + 1, inf = 1e15, mod = 998244353;
      |                              ^~~~

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