Submission #1226955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226955		lmquan	Snake Escaping (JOI18_snake_escaping)	C++20	100 / 100	535 ms	20740 KiB

snake_escaping

#define taskname "SnakeEscaping"
#include <bits/stdc++.h>
using namespace std;

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int l, q;
  cin >> l >> q;
  vector<int> f(1 << l, 0), g(1 << l, 0), a(1 << l);
  for (int i = 0; i < (1 << l); i++) {
    char x;
    cin >> x;
    a[i] = (x - '0');
    f[i] = g[i] = (x - '0');
  }
  for (int i = 0; i < l; i++) {
    for (int j = 0; j < (1 << l); j++) {
      if (j & (1 << i)) {
        f[j] += f[j ^ (1 << i)];
      }
    }
  }
  for (int i = 0; i < l; i++) {
    for (int j = (1 << l) - 1; j >= 0; j--) {
      if (!(j & (1 << i))) {
        g[j] += g[j | (1 << i)];
      }
    }
  }

  while (q--) {
    string t;
    cin >> t;
    int cnt0 = 0, cnt1 = 0, cnt2 = 0, s0 = 0, s1 = 0, s2 = 0;
    for (int i = 0; i < t.size(); i++) {
      if (t[i] == '0') {
        cnt0++;
        s0 |= (1 << (t.size() - 1 - i));
      } else if (t[i] == '1') {
        cnt1++;
        s1 |= (1 << (t.size() - 1 - i));
      } else {
        cnt2++;
        s2 |= (1 << (t.size() - 1 - i));
      }
    }

    if (!cnt2) {
      int val = 0;
      for (int i = t.size() - 1; i >= 0; i--) {
        if (t[i] == '1') {
          val |= (1 << (t.size() - 1 - i));
        }
      }
      cout << a[val] << '\n';
      continue;
    }

    int result = 0;
    if (cnt0 == min({cnt0, cnt1, cnt2})) {
      for (int i = s0;; i = (i - 1) & s0) {
        result += (__builtin_popcount(i) & 1 ? -1 : 1) * g[i | s1];
        if (i == 0) {
          break;
        }
      }
    } else if (cnt1 == min({cnt0, cnt1, cnt2})) {
      for (int i = s1;; i = (i - 1) & s1) {
        result += ((__builtin_popcount(i) + cnt1) & 1 ? -1 : 1) * f[i | s2];
        if (i == 0) {
          break;
        }
      }
    } else {
      for (int i = s2;; i = (i - 1) & s2) {
        result += a[i | s1];
        if (i == 0) {
          break;
        }
      }
    }
    cout << result << '\n';
  }

  return 0;
}

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:7:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
snake_escaping.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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