oj.uz

Submission #1054845

# Submission time Handle Problem Language Result Execution time Memory
1054845 2024-08-12T12:36:26 Z nima_aryan Snake Escaping (JOI18_snake_escaping) C++17
0 / 100
 1 ms 348 KB 
/**
 *    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(u) % 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;
}

Compilation message

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -