제출 #1054851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1054851		nima_aryan	Snake Escaping (JOI18_snake_escaping)	C++17	100 / 100	351 ms	39412 KiB

snake_escaping

/**
 *    author:  NimaAryan
 *    created: 2024-08-12 13:06:22  
**/
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")  // don't trust it

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int L, Q;
  cin >> L >> Q;

  string S;
  cin >> S;

  vector<int> sub(1 << L);
  for (int i = 0; i < S.size(); ++i) {
    sub[i] = (S[i] - '0');
  }
  for (int i = 0; i < L; ++i) {
    for (int u = (1 << L) - 1; u >= 0; --u) {
      if (u >> i & 1) {
        sub[u] += sub[u ^ (1 << i)];
      }
    }
  }

  vector<int> super(1 << L);
  for (int i = 0; i < S.size(); ++i) {
    super[i] = (S[i] - '0');
  }
  for (int i = 0; i < L; ++i) {
    for (int u = 0; u < (1 << L); ++u) {
      if (!(u >> i & 1)) {
        super[u] += super[u ^ (1 << i)];
      }
    }
  }

  while (Q--) {
    string T;
    cin >> T;
    reverse(T.begin(), T.end());
    int cnt0 = count(T.begin(), T.end(), '0');
    int cnt1 = count(T.begin(), T.end(), '1');
    if (cnt0 <= L / 3) {
      int v = 0;
      int u = 0;
      for (int i = 0; i < L; ++i) {
        if (T[i] == '1') {
          v ^= (1 << i);
        } else if (T[i] == '0') {
          u ^= (1 << i);
        }
      }
      int ans = 0;
      for (int s = u; s > 0; s = (s - 1) & u) {
        ans += (__builtin_popcount(s) % 2 == 0 ? +1 : -1) * super[v | s];
      }
      ans += super[v];
      cout << ans << "\n";
    } else if (cnt1 <= L / 3) {
      int v = 0;
      int u = 0;
      for (int i = 0; i < L; ++i) {
        if (T[i] == '?') {
          v ^= (1 << i);
        } else if (T[i] == '1') {
          u ^= (1 << i);
        }
      }
      int ans = 0;
      for (int s = u; s > 0; s = (s - 1) & u) {
        ans += (__builtin_popcount(s) % 2 == 0 ? +1 : -1) * sub[v | (u - s)];
      }
      ans += sub[v | u];
      cout << ans << "\n";
    } else {
      int u = 0;
      int v = 0;
      for (int i = 0; i < L; ++i) {
        if (T[i] == '?') {
          u ^= (1 << i);
        } else if (T[i] == '1') {
          v ^= (1 << i);
        }
      }
      int ans = 0;
      for (int s = u; s > 0; s = (s - 1) & u) {
        ans += S[v | s] - '0';
      }
      ans += S[v] - '0';
      cout << ans << "\n";
    }
  }

  return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for (int i = 0; i < S.size(); ++i) {
      |                   ~~^~~~~~~~~~
snake_escaping.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int i = 0; i < S.size(); ++i) {
      |                   ~~^~~~~~~~~~

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