tests/xor_basis.test.cpp

• View this file on GitHub
• Last update: 2025-01-25 08:45:50+09:00

Depends on

• Assertion macro (tools/assert_that.hpp)
• chmin function (tools/chmin.hpp)
• Basis of xor (tools/xor_basis.hpp)

Code

// competitive-verifier: STANDALONE

#include <iostream>
#include <vector>
#include <iterator>
#include "tools/assert_that.hpp"
#include "tools/xor_basis.hpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  {
    std::vector<ll> in({1, 1, 2, 4});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 3);
  }
  {
    std::vector<ll> in({1, 1, 2, 1});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 2);
  }
  {
    std::vector<ll> in({1, 1, 2, 3});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 2);
  }
  {
    std::vector<ll> in({1, 2, 3});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 2);
  }
  {
    std::vector<ll> in({1});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 1);
  }
  {
    std::vector<ll> in;
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 0);
  }

  return 0;
}

#line 1 "tests/xor_basis.test.cpp"
// competitive-verifier: STANDALONE

#include <iostream>
#include <vector>
#include <iterator>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    ::std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    ::std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/xor_basis.hpp"



#include <type_traits>
#line 1 "tools/chmin.hpp"



#line 5 "tools/chmin.hpp"
#include <utility>

namespace tools {

  template <typename M, typename N>
  bool chmin(M& lhs, const N& rhs) {
    bool updated;
    if constexpr (::std::is_integral_v<M> && ::std::is_integral_v<N>) {
      updated = ::std::cmp_less(rhs, lhs);
    } else {
      updated = rhs < lhs;
    }
    if (updated) lhs = rhs;
    return updated;
  }
}


#line 7 "tools/xor_basis.hpp"

// Source: https://twitter.com/noshi91/status/1200702280128856064
// License: unknown
// Author: noshi91

namespace tools {
  template <typename InputIterator, typename OutputIterator>
  void xor_basis(const InputIterator& begin, const InputIterator& end, OutputIterator result) {
    using T = ::std::decay_t<decltype(*begin)>;

    ::std::vector<T> basis;
    for (auto it = begin; it != end; ++it) {
      T e = *it;
      for (const T& b : basis) {
        ::tools::chmin(e, e ^ b);
      }
      if (e != 0) {
        basis.push_back(e);
      }
    }

    for (const T& b : basis) {
      *result = b;
      ++result;
    }
  }
}


#line 8 "tests/xor_basis.test.cpp"

using ll = long long;

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  {
    std::vector<ll> in({1, 1, 2, 4});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 3);
  }
  {
    std::vector<ll> in({1, 1, 2, 1});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 2);
  }
  {
    std::vector<ll> in({1, 1, 2, 3});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 2);
  }
  {
    std::vector<ll> in({1, 2, 3});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 2);
  }
  {
    std::vector<ll> in({1});
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 1);
  }
  {
    std::vector<ll> in;
    std::vector<ll> out;
    tools::xor_basis(in.begin(), in.end(), std::back_inserter(out));
    assert_that(out.size() == 0);
  }

  return 0;
}

Back to top page