Submission #654657

#	Time	Username	Problem	Language	Result	Execution time	Memory
654657		lunchbox1	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	696 ms	43472 KiB

snake_escaping

/*
 Snake Escaping
 https://oj.uz/problem/view/JOI18_snake_escaping
*/
#include <bits/stdc++.h>
using namespace std;

const int L = 20, N = 1 << L;

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 int l, q; cin >> l >> q;
 string s; cin >> s;
 int n = 1 << l;
 static int f[N], g[N], c[N];
 for (int i = 0; i < n; i++)
  f[i] += s[i] - '0', g[i] += s[i] - '0';
 for (int i = 1; i < n; i++)
  c[i] = c[i & (i - 1)] + 1;
 for (int b = 0; b < l; b++)
  for (int i = 0; i < n; i++)
   if (i >> b & 1) {
    f[i] += f[i ^ (1 << b)];
    g[i ^ (1 << b)] += g[i];
   }
 while (q--) {
  string t; cin >> t;
  reverse(t.begin(), t.end());
  int i0 = 0, i1 = 0, iq = 0;
  for (int b = 0; b < l; b++)
   if (t[b] == '0') i0 |= 1 << b;
   else if (t[b] == '1') i1 |= 1 << b;
   else iq |= 1 << b;
  int v = 0;
  if (c[iq] <= 7) {
   for (int t = iq; ; t = (t - 1) & iq) {
    v += s[t | i1] - '0';
    if (t == 0) break;
   }
  } else if (c[i0] <= 7) {
   for (int t = i0; ; t = (t - 1) & i0) {
    v += (c[t] % 2 ? -1 : +1) * g[t | i1];
    if (t == 0) break;
   }
  } else {
   for (int t = i1; ; t = (t - 1) & i1) {
    v += (c[t] % 2 ? -1 : +1) * f[(t ^ i1) | iq];
    if (t == 0) break;
   }
  }
  cout << v << '\n';
 }
 return 0;
}

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