Submission #1054806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054806		nima_aryan	Snake Escaping (JOI18_snake_escaping)	C++17	75 / 100	2049 ms	36340 KiB

snake_escaping

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

using namespace std;

#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 ans = 0;
      for (int u = 0; u < (1 << cnt0); ++u) {
        int v = 0;
        for (int i = 0, j = 0; i < L; ++i) {
          if (T[i] == '0') {
            if (u >> j & 1) {
              v ^= (1 << i);
            } else {

            }
            ++j;
          } else if (T[i] == '1') {
            v ^= (1 << i);
          } else if (T[i] == '?') {

          }
        }
        ans += (__builtin_popcount(u) % 2 == 0 ? +1 : -1) * super[v];
      }
      cout << ans << "\n";
    } else if (cnt1 <= L / 3) {
      int ans = 0;
      for (int u = 0; u < (1 << cnt1); ++u) {
        int v = 0;
        for (int i = 0, j = 0; i < L; ++i) {
          if (T[i] == '1') {
            if (u >> j & 1) {

            } else {
              v ^= (1 << i) * 1;
            }
            ++j;
          } else if (T[i] == '0') {

          } else if (T[i] == '?') {
            v ^= (1 << i);
          }
        }
        ans += (__builtin_popcount(u) % 2 == 0 ? +1 : -1) * sub[v];
      }
      cout << ans << "\n";
    } else {
      int u = 0;
      for (int i = 0; i < L; ++i) {
        if (T[i] == '?') {
          u ^= (1 << i);
        }
      }
      int ans = 0;
      auto add = [&](int s) {
        int v = 0;
        for (int i = 0; i < L; ++i) {
          if (T[i] == '?') {
            if (s >> i & 1) {
              v ^= (1 << i);
            } else {
              
            }
          } else if (T[i] == '0') {
            
          } else {
            v ^= (1 << i);
          }
        }
        ans += S[v] - '0';
      };
      for (int s = u; s > 0; s = (s - 1) & u) {
        add(s);
      }
      add(0);
      cout << ans << "\n";
    }
  }

  return 0;
}

Compilation message (stderr)

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