Submission #1144911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144911		fryingduc	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	814 ms	17740 KiB

snake_escaping

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e6 + 6;
const int MASK = (1 << 20) + 5;
int l, q, n;
string s;
int f[MASK], g[MASK];

void solve() {
  cin >> l >> q >> s;
  n = (1 << l);
  for(int i = 0; i < n; ++i) {
    f[i] = g[i] = s[i] - '0';
  }
  for(int i = 0; i < l; ++i) {
    for(int mask = 0; mask < n; ++mask) {
      if(mask >> i & 1) continue;
      g[mask] += g[mask ^ (1 << i)];
    }
    for(int mask = n - 1; mask >= 0; --mask) {
      if(mask >> i & 1) {
        f[mask] += f[mask ^ (1 << i)];
      }
    }
  }
  string t;
  int third = l / 3, res = 0;
  int c0 = 0, c1 = 0;
  while(q--) {
    cin >> t;
    reverse(t.begin(), t.end());
    res = 0;
    c0 = 0, c1 = 0;
    for(int i = 0; i < l; ++i) {
      if(t[i] == '0') ++c0;
      else if(t[i] == '1') ++c1;
    }
    vector<int> pos;
    if(l - c0 - c1 <= third) {
      int org_mask = 0;
      for(int i = 0; i < l; ++i) {
        if(t[i] == '?') {
          pos.push_back(i);
        } else if(t[i] == '1') {
          org_mask |= (1 << i);
        }
      }
      int sz = (int)pos.size();
      for(int mask = 0; mask < (1 << sz); ++mask) {
        int cur_mask = org_mask;
        for(int i = 0; i < sz; ++i) {
          if(mask >> i & 1) {
            cur_mask |= (1 << pos[i]);
          }
        }
        res += s[cur_mask] - '0';
      }
    } else if(c0 <= third) {
      int org_mask = 0;
      for(int i = 0; i < l; ++i) {
        if(t[i] == '0') {
          pos.push_back(i);
        } else if(t[i] == '1') {
          org_mask |= (1 << i);
        }
      }
      int sz = (int)pos.size();
      for(int mask = 0; mask < (1 << sz); ++mask) {
        int cur_mask = org_mask;
        for(int i = 0; i < sz; ++i) {
          if(mask >> i & 1) {
            cur_mask |= (1 << pos[i]);
          }
        }
        int sign = (__builtin_popcount(mask) & 1 ? -1 : 1);
        res += sign * g[cur_mask];
      }
    } else {
      int org_mask = 0;
      for(int i = 0; i < l; ++i) {
        if(t[i] == '1') {
          pos.push_back(i);
          org_mask |= (1 << i);
        } else if(t[i] == '?') {
          org_mask |= (1 << i);
        }
      }
      int sz = (int)pos.size();
      for(int mask = 0; mask < (1 << sz); ++mask) {
        int cur_mask = org_mask;
        for(int i = 0; i < sz; ++i) {
          if(mask >> i & 1) {
            cur_mask ^= (1 << pos[i]);
          }
        }
        int sign = (__builtin_popcount(mask) & 1 ? -1 : 1);
        res += sign * f[cur_mask];
      }
    }
    cout << res << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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