제출 #649571

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
649571		Alex_tz307	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	788 ms	39408 KiB

snake_escaping

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int l, q;
  string s;
  cin >> l >> q >> s;
  int n = (1 << l);
  vector<int> sub(n), super(n);
  for (int mask = 0; mask < n; ++mask) {
    sub[mask] = (s[mask] - '0');
    super[mask] = (s[mask] - '0');
  }
  for (int bit = 0; bit < l; ++bit) {
    for (int mask = 0; mask < n; ++mask) {
      if (mask & (1 << bit)) {
        sub[mask] += sub[mask ^ (1 << bit)];
      } else {
        super[mask] += super[mask | (1 << bit)];
      }
    }
  }
  for (int qq = 0; qq < q; ++qq) {
    string t;
    cin >> t;
    int mask0 = 0, mask1 = 0, maskq = 0;
    for (int i = 0; i < l; ++i) {
      if (t[i] == '0') {
        mask0 |= (1 << (l - i - 1));
      } else if (t[i] == '1') {
        mask1 |= (1 << (l - i - 1));
      } else {
        maskq |= (1 << (l - i - 1));
      }
    }
    int sum = 0, mask;
    if (__builtin_popcount(maskq) <= l / 3) {
      mask = maskq;
      while (mask) {
        sum += (s[mask1 | mask] - '0');
        mask = (mask - 1) & maskq;
      }
      sum += (s[mask1] - '0');
    } else if (__builtin_popcount(mask0) <= l / 3) {
      mask = mask0;
      while (mask) {
        if (__builtin_popcount(mask) % 2 == 0) {
          sum += super[mask | mask1];
        } else {
          sum -= super[mask | mask1];
        }
        mask = (mask - 1) & mask0;
      }
      sum += super[mask1];
    } else {
      int N = __builtin_popcount(mask1);
      mask = mask1;
      while (mask) {
        if ((N - __builtin_popcount(mask)) % 2 == 0) {
          sum += sub[mask | maskq];
        } else {
          sum -= sub[mask | maskq];
        }
        mask = (mask - 1) & mask1;
      }
      if (N % 2 == 0) {
        sum += sub[maskq];
      } else {
        sum -= sub[maskq];
      }
    }
    cout << sum << '\n';
  }
  return 0;
}

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