test/yukicoder/184/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: https://yukicoder.me/problems/no/184
• Link: View error logs on GitHub Actions

Depends on

• Input vector (Mylib/IO/input_vector.cpp)
• Gaussian elimination (Mod2) (Mylib/LinearAlgebra/gaussian_elimination_binary.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/184"

#include <bitset>
#include <iostream>
#include <vector>
#include "Mylib/IO/input_vector.cpp"
#include "Mylib/LinearAlgebra/gaussian_elimination_binary.cpp"

namespace hl = haar_lib;

int main() {
  int n;
  std::cin >> n;
  auto a = hl::input_vector<int64_t>(n);

  int rank = hl::gaussian_elimination(std::vector<std::bitset<64>>(a.begin(), a.end()));

  std::cout << (1LL << rank) << "\n";

  return 0;
}

#line 1 "test/yukicoder/184/main.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/184"

#include <bitset>
#include <iostream>
#include <vector>
#line 4 "Mylib/IO/input_vector.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> input_vector(int N) {
    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) std::cin >> ret[i];
    return ret;
  }

  template <typename T>
  std::vector<std::vector<T>> input_vector(int N, int M) {
    std::vector<std::vector<T>> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
    return ret;
  }
}  // namespace haar_lib
#line 3 "Mylib/LinearAlgebra/gaussian_elimination_binary.cpp"
#include <utility>
#line 5 "Mylib/LinearAlgebra/gaussian_elimination_binary.cpp"

namespace haar_lib {
  template <size_t N>
  int gaussian_elimination(std::vector<std::bitset<N>> &m) {
    const int n = m.size();
    int rank    = 0;

    for (size_t j = 0; j < N; ++j) {
      int pivot = -1;

      for (int i = rank; i < n; ++i) {
        if (m[i][j]) {
          pivot = i;
          break;
        }
      }

      if (pivot == -1) continue;

      std::swap(m[pivot], m[rank]);

      for (int i = 0; i < n; ++i) {
        if (i != rank and m[i][j]) m[i] ^= m[rank];
      }
      ++rank;
    }

    return rank;
  }

  template <size_t N>
  int gaussian_elimination(std::vector<std::bitset<N>> &&m) {
    return gaussian_elimination(m);
  }
}  // namespace haar_lib
#line 8 "test/yukicoder/184/main.test.cpp"

namespace hl = haar_lib;

int main() {
  int n;
  std::cin >> n;
  auto a = hl::input_vector<int64_t>(n);

  int rank = hl::gaussian_elimination(std::vector<std::bitset<64>>(a.begin(), a.end()));

  std::cout << (1LL << rank) << "\n";

  return 0;
}

Back to top page