tests/mex.test.cpp

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

Depends on

Code

// competitive-verifier: STANDALONE

#include <cstdlib>
#include <iostream>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/mex.hpp"

using ll = long long;

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

  std::vector<ll> v({1000000000000000000, 2, 1, 0});
  assert_that(tools::mex(v.begin(), v.end()) == 3);
  v = std::vector<ll>({3, 3, 2, 2, 1, 1, 0});
  assert_that(tools::mex(v.begin(), v.end()) == 4);
  v = std::vector<ll>({3, 2, 0, 4, 1});
  assert_that(tools::mex(v.begin(), v.end()) == 5);
  v = std::vector<ll>({3, 2, 4, 1});
  assert_that(tools::mex(v.begin(), v.end()) == 0);

  return 0;
}

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

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



#line 6 "tools/assert_that.hpp"

#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/mex.hpp"



#include <type_traits>
#include <utility>
#line 7 "tools/mex.hpp"
#include <cstddef>
#include <cassert>
#include <algorithm>

namespace tools {

  template <typename InputIterator>
  ::std::decay_t<decltype(*::std::declval<InputIterator>())> mex(InputIterator begin, InputIterator end) {
    using T = ::std::decay_t<decltype(*::std::declval<InputIterator>())>;
    const ::std::vector<T> orig(begin, end);
    const ::std::size_t n = orig.size();

    assert(::std::all_of(orig.begin(), orig.end(), [](const auto& o) { return o >= 0; }));

    ::std::vector<bool> exists(n, false);
    for (const ::std::size_t o : orig) {
      if (o < n) {
        exists[o] = true;
      }
    }
    for (::std::size_t i = 0; i < n; ++i) {
      if (!exists[i]) {
        return i;
      }
    }
    return n;
  }
}


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

using ll = long long;

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

  std::vector<ll> v({1000000000000000000, 2, 1, 0});
  assert_that(tools::mex(v.begin(), v.end()) == 3);
  v = std::vector<ll>({3, 3, 2, 2, 1, 1, 0});
  assert_that(tools::mex(v.begin(), v.end()) == 4);
  v = std::vector<ll>({3, 2, 0, 4, 1});
  assert_that(tools::mex(v.begin(), v.end()) == 5);
  v = std::vector<ll>({3, 2, 4, 1});
  assert_that(tools::mex(v.begin(), v.end()) == 0);

  return 0;
}