test/verify/yukicoder-184.test.cpp

• View this file on GitHub
• Last update: 2026-08-10 14:58:15+00:00
• Problem: https://yukicoder.me/problems/no/184

Depends on

• math/matrix/binary-basis.hpp

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/184

#include <cstdint>
#include <iostream>

#include "../../math/matrix/binary-basis.hpp"

using namespace std;

int main() {
  int N;
  cin >> N;
  BinaryBasis<int64_t> bb;
  for (int i = 0; i < N; i++) {
    int64_t x;
    cin >> x;
    bb.add(x);
  }
  cout << (1LL << bb.size()) << "\n";
}

#line 1 "test/verify/yukicoder-184.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/184

#include <cstdint>
#include <iostream>

#line 2 "math/matrix/binary-basis.hpp"

#include <algorithm>
#include <cstddef>
#line 6 "math/matrix/binary-basis.hpp"
#include <iterator>
#include <utility>
#include <vector>

template <typename T>
struct BinaryBasis {
  std::vector<T> basis;
  bool update;

  BinaryBasis() : update(false) {}

  bool add(T bit) {
    for (auto& p : basis) {
      bit = std::min(bit, bit ^ p);
    }
    if (bit) {
      basis.emplace_back(bit);
      return update = true;
    } else {
      return false;
    }
  }

  bool check(T bit) const {
    for (auto& p : basis) {
      bit = std::min(bit, bit ^ p);
    }
    return bit == 0;
  }

  void normalize() {
    sweep();
    for (int i = (int)basis.size() - 1; i >= 0; i--) {
      for (int j = i - 1; j >= 0; j--)
        basis[i] = std::min(basis[i], basis[i] ^ basis[j]);
    }
  }

  void sweep() {
    if (std::exchange(update, false)) {
      std::sort(std::begin(basis), std::end(basis));
    }
  }

  bool operator==(BinaryBasis<T>& a) {
    normalize(), a.normalize();
    return basis == a.basis;
  }

  T get_kth(std::int64_t k) { /* 0-indexed */
    if ((1LL << basis.size()) <= k) {
      return -1;
    }
    T ret = T();
    sweep();
    for (int i = (int)basis.size() - 1; i >= 0; i--) {
      if (k < (1LL << i)) {
        ret = std::min(ret, ret ^ basis[i]);
      } else {
        k -= 1LL << i;
        ret = std::max(ret, ret ^ basis[i]);
      }
    }
    return ret;
  }

  std::size_t size() const { return basis.size(); }
};
#line 7 "test/verify/yukicoder-184.test.cpp"

using namespace std;

int main() {
  int N;
  cin >> N;
  BinaryBasis<int64_t> bb;
  for (int i = 0; i < N; i++) {
    int64_t x;
    cin >> x;
    bb.add(x);
  }
  cout << (1LL << bb.size()) << "\n";
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample01	AC	2 ms	4 MB
g++	00_sample02	AC	2 ms	4 MB
g++	00_sample03	AC	2 ms	4 MB
g++	10_random_small01	AC	2 ms	4 MB
g++	10_random_small02	AC	2 ms	4 MB
g++	10_random_small03	AC	2 ms	4 MB
g++	10_random_small04	AC	2 ms	4 MB
g++	10_random_small05	AC	2 ms	4 MB
g++	20_random_large01	AC	38 ms	3 MB
g++	20_random_large02	AC	10 ms	4 MB
g++	20_random_large03	AC	30 ms	4 MB
g++	20_random_large04	AC	22 ms	4 MB
g++	20_random_large05	AC	44 ms	3 MB
g++	20_random_large06	AC	48 ms	4 MB
g++	20_random_large07	AC	28 ms	4 MB
g++	20_random_large08	AC	52 ms	4 MB
g++	20_random_large09	AC	43 ms	4 MB
g++	20_random_large10	AC	47 ms	4 MB
g++	30_corner01	AC	2 ms	4 MB
g++	30_corner02	AC	2 ms	4 MB
g++	30_corner03	AC	12 ms	4 MB
g++	30_corner04	AC	65 ms	4 MB
g++	30_corner05	AC	54 ms	4 MB
g++	40_random_small01	AC	3 ms	4 MB
g++	40_random_small02	AC	2 ms	4 MB
g++	40_random_small03	AC	2 ms	4 MB
g++	40_random_small04	AC	2 ms	4 MB
g++	40_random_small05	AC	2 ms	4 MB
g++	50_random_large01	AC	34 ms	4 MB
g++	50_random_large02	AC	46 ms	4 MB
g++	50_random_large03	AC	41 ms	4 MB
g++	50_random_large04	AC	39 ms	3 MB
g++	50_random_large05	AC	45 ms	3 MB
g++	system_test1	AC	53 ms	3 MB
g++	system_test2	AC	52 ms	4 MB
g++	system_test3	AC	55 ms	3 MB
g++	system_test4	AC	91 ms	3 MB
clang++	00_sample01	AC	2 ms	4 MB
clang++	00_sample02	AC	2 ms	4 MB
clang++	00_sample03	AC	2 ms	4 MB
clang++	10_random_small01	AC	2 ms	4 MB
clang++	10_random_small02	AC	2 ms	4 MB
clang++	10_random_small03	AC	2 ms	4 MB
clang++	10_random_small04	AC	2 ms	4 MB
clang++	10_random_small05	AC	2 ms	4 MB
clang++	20_random_large01	AC	38 ms	4 MB
clang++	20_random_large02	AC	10 ms	4 MB
clang++	20_random_large03	AC	29 ms	4 MB
clang++	20_random_large04	AC	22 ms	4 MB
clang++	20_random_large05	AC	44 ms	4 MB
clang++	20_random_large06	AC	48 ms	4 MB
clang++	20_random_large07	AC	28 ms	4 MB
clang++	20_random_large08	AC	51 ms	4 MB
clang++	20_random_large09	AC	43 ms	4 MB
clang++	20_random_large10	AC	47 ms	4 MB
clang++	30_corner01	AC	2 ms	4 MB
clang++	30_corner02	AC	2 ms	4 MB
clang++	30_corner03	AC	11 ms	4 MB
clang++	30_corner04	AC	53 ms	4 MB
clang++	30_corner05	AC	53 ms	4 MB
clang++	40_random_small01	AC	2 ms	4 MB
clang++	40_random_small02	AC	2 ms	4 MB
clang++	40_random_small03	AC	2 ms	4 MB
clang++	40_random_small04	AC	2 ms	4 MB
clang++	40_random_small05	AC	2 ms	4 MB
clang++	50_random_large01	AC	33 ms	4 MB
clang++	50_random_large02	AC	46 ms	4 MB
clang++	50_random_large03	AC	41 ms	4 MB
clang++	50_random_large04	AC	35 ms	4 MB
clang++	50_random_large05	AC	43 ms	4 MB
clang++	system_test1	AC	52 ms	4 MB
clang++	system_test2	AC	51 ms	4 MB
clang++	system_test3	AC	53 ms	4 MB
clang++	system_test4	AC	52 ms	4 MB

Back to top page