Submission #966962

#	Time	Username	Problem	Language	Result	Execution time	Memory
966962		efedmrlr	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1724 ms	42292 KiB

snake_escaping

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
    
using namespace std;
    
    
#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
    
    
void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
    
    
const int INF = 1e9+500;
const int N = 20;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,q;
array<int, (1 << N)> a, dp, dpr;
int RVSR;
inline void solve() {
    cin>>n>>q;
    RVSR = (1 << n) - 1;
    for(int i = 0; i < (1 << n); i++) {
        char tmp;
        cin >> tmp;
        a[i] = dp[i] = dpr[i ^ RVSR] = tmp - '0';
    }
    
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < (1 << n); i++) {
            if(i & (1 << k)) {
                dp[i] += dp[i ^ (1 << k)];
                dpr[i] += dpr[i ^ (1 << k)];
            }
        }
    }
    // for(int i = 0; i < (1 << n); i++) {
    //     cout << "i:" << i <<" dp:" << dp[i] << " dpr:" << dpr[i] << "\n";
    // }
    REP(z, q) {
        string s;
        cin >> s;
        reverse(all(s));
        int cnt0 = 0, cnt1 = 0;
        for(char c : s) {
            if(c == '0') cnt0++;
            else if(c == '1') cnt1++;
        }
        int ans = 0;
        if(cnt1 + cnt0 >= 14) {
            int x = 0;
            int y = 0;
            for(int i = 0; i < n; i++) {
                if(s[i] == '?') y += (1 << i);
                else if(s[i] == '1') x += (1 << i);
            }
            for(int i = y; ; i = (i - 1) & y) {
                ans += a[x + i];
                if(i == 0) break;
            }
        }
        else if(cnt1 > cnt0) {   // use reverse
            int x = 0;
            int y = 0;
            for(int i = 0; i < n; i++) {
                if(s[i] != '1') x += (1 << i);
                if(s[i] == '0') {
                    y += (1 << i);
                }
            }
            for(int i = y; ; i = (i - 1) & y) {
                if(__popcount(i) & 1) {
                    ans -= dpr[x ^ i];
                }
                else {
                    ans += dpr[x ^ i];
                }
                if(i == 0) break;
            }
        }
        else {
            int x = 0;
            int y = 0;
            for(int i = 0; i < n; i++) {
                if(s[i] != '0') x += (1 << i);
                if(s[i] == '1') {
                    y += (1 << i);
                }
            }
            for(int i = y; ; i = (i - 1) & y) {
                if(__popcount(i) & 1) {
                    ans -= dp[x ^ i];
                }
                else {
                    ans += dp[x ^ i];
                }
                if(i == 0) break;
            }
        }
        cout << ans << endl;
    }
    
    
    
}
    
signed main() {
    
    fastio();
    solve();
    
}

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