Submission #1177949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177949		akamizane	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	404 ms	26116 KiB

snake_escaping

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

#define debug(...) 42

const int MOD = 998244353;

void solve(){
    int L, Q;
    cin >> L >> Q;
    int n = 1 << L;
    vector<int> S(n), sup(n), sub(n), btcnt(n, 0);
    string s;
    cin >> s;  

    for (int i = 0; i < n; i++) {
        S[i] = s[i] - '0';
        sup[i] = S[i];
        sub[i] = S[i];
        btcnt[i] = __builtin_popcount(i);
    }
    
    for (int b = 0; b < L; b++) {
        for (int m = 0; m < n; m++) {
            if (((m >> b) & 1) == 0)
                sup[m] += sup[m ^ (1 << b)];
            else
                sub[m] += sub[m ^ (1 << b)];
        }
    }
    

    
    for (int i = 0; i < Q; i++) {
        cin >> s; 
        int A = 0, B = 0, C = 0;
        int ca = 0, cb = 0, cc = 0;
        long long ans = 0;
        
        for (int j = 0; j < L; j++) {
            int bit = 1 << (L - j - 1);
            if (s[j] == '0') {
                A |= bit;
                ca++;
            } else if (s[j] == '1') {
                B |= bit;
                cb++;
            } else {
                C |= bit;
                cc++;
            }
        }
        
        if (ca <= cb && ca <= cc) {

            for (int m = A; m; m = (m - 1) & A) {
                int parity = btcnt[m] & 1; 
                ans += (1 - 2 * parity) * (long long) sup[B | m];
            }
            ans += sup[B];
        } else if (cb <= ca && cb <= cc) {

            for (int m = B; m; m = (m - 1) & B) {
                int parity = btcnt[m] & 1;
                ans += (1 - 2 * parity) * (long long) sub[C | (B ^ m)];
            }
            ans += sub[C | B];
        } else {
            for (int m = C; m; m = (m - 1) & C) {
                ans += S[m | B];
            }
            ans += S[B];
        }
        cout << ans << "\n";
    }
    
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int tt = 1;
  // cin >> tt;
  while (tt--){
    solve();
  }
  return 0;
}

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