Submission #861864

#	Time	Username	Problem	Language	Result	Execution time	Memory
861864		NeroZein	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	1365 ms	42196 KiB

snake_escaping

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int l, q;
  cin >> l >> q;
  int n = (1 << l); 
  vector<int> a(n); 
  for (int i = 0; i < n; ++i) {
    char c;
    cin >> c;
    a[i] = c - '0'; 
  }
  vector<int> sub(n); 
  for (int i = 0; i < n; ++i) {
    sub[i] = a[i]; 
  }
  for (int j = 0; j < l; ++j) {
    for (int s = 0; s < n; ++s) {
      if (s >> j & 1) {
        sub[s] += sub[s ^ (1 << j)];
      }
    }
  }
  vector<int> sup(n);
  for (int i = 0; i < n; ++i) {
    sup[i] = a[i];
  }
  for (int j = 0; j < l; ++j) {
    for (int s = 0; s < n; ++s) {
      if (!(s >> j & 1)) {
        sup[s] += sup[s | (1 << j)];
      }
    }
  }
  while (q--) {
    string qs;
    cin >> qs;
    int msk = 0;
    vector<int> zeros, ones, qm;
    for (int i = 0; i < l; ++i) {
      if (qs[i] == '0') {
        zeros.push_back(l - i - 1);
      } else if (qs[i] == '1') {
        ones.push_back(l - i - 1); 
        msk |= 1 << (l - i - 1);
      } else {
        qm.push_back(l - i - 1);
      }
    }
    int ans = 0; 
    if (qm.size() <= 6) {
      int m = (int) qm.size();
      for (int i = 0; i < (1 << m); ++i) {
        int msk2 = 0;
        for (int j = 0; j < m; ++j) {
          if (i >> j & 1) {
            msk2 |= 1 << qm[j]; 
          }
        }
        ans += a[msk | msk2]; 
      }
    } else if (ones.size() <= 6) {
      int m = (int) ones.size(); 
      for (int i = 0; i < (int) qs.size(); ++i) {
        if (qs[i] == '?') {
          msk |= 1 << (l - i - 1); 
        } else if (qs[i] == '1') {
          msk ^= 1 << (l - i - 1); 
        }
      }
      for (int i = 0; i < (1 << m); ++i) {
        int msk2 = 0; 
        bool even = true; //is off even or not
        for (int j = 0; j < m; ++j) {
          if (!(i >> j & 1)) {
            even ^= 1; 
          } else {
            msk2 |= 1 << ones[j];             
          }
        }
        ans += (even ? 1 : -1) * sub[msk | msk2];
      }
    } else {
      int m = zeros.size();
      for (int i = 0; i < (1 << m); ++i) {
        int msk2 = 0;
        bool even = true; 
        for (int j = 0; j < m; ++j) {
          if (i >> j & 1) {
            even ^= 1; 
            msk2 |= 1 << zeros[j];
          }
        }
        ans += (even ? 1 : -1) * sup[msk | msk2];
      }
    }
    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