Submission #1177997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177997		akamizane	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	383 ms	22020 KiB

snake_escaping

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

#define debug(...) 42


void solve(){
    int l, q;
    cin >> l >> q;
    int n = 1 << l;
    vector<int> val(n), sub(n), sup(n);
    string s;
    cin >> s;
    for (int i = 0; i < n; i++){
      val[i] = sub[i] = sup[i] = s[i] - '0';
    }
    debug(val);
    for (int i = 0; i < l; i++){
      for (int mask = 0; mask < (1 << l); mask++){
        if (mask >> i & 1) sub[mask] += sub[mask ^ (1 << i)];
        else sup[mask] += sup[mask ^ (1 << i)];
      }
    }
    while(q--){
      cin >> s;
      int one = 0, zero = 0, ask = 0;
      for (int i = 0; i < l; i++){
        if (s[i] == '1') one |= 1 << (l - 1 - i);
        else if (s[i] == '0') zero |= 1 << (l - 1 - i);
        else if (s[i] == '?') ask |= 1 << (l - 1 - i);
      }
      debug(s, one, zero, ask);
      int ans = 0;
      if (__builtin_popcount(ask) <= l / 3){
        for (int x = ask; x >= 0; x = (x - 1) & ask){
          ans += val[one ^ x];
          if (x == 0) break;
        }
      }
      else if (__builtin_popcount(zero) <= l / 3){
        for (int x = zero; x >= 0; x = (x - 1) & zero){
          if (__builtin_popcount(x) & 1){
            ans -= sup[x ^ one];
          }
          else ans += sup[x ^ one];
          if (x == 0) break;
        }
      }
      else{
        for (int x = one; x >= 0; x = (x - 1) & one){
          if (__builtin_popcount(x ^ one) & 1){
            ans -= sub[x ^ ask];
          }
          else ans += sub[x ^ ask];
          if (x == 0) break;
        }
      }
      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