tests/kth_smallest_by_oracle.test.cpp

View this file on GitHub
Last update: 2025-12-07 12:31:51+09:00

Depends on

Code

// competitive-verifier: STANDALONE

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

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

  const std::vector<int> S{1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9};
  const auto f = [&](const int x) {
    return std::distance(S.begin(), std::ranges::upper_bound(S, x));
  };

  assert_that(tools::kth_smallest_by_oracle(1, f, 1, 9) == 1);
  assert_that(tools::kth_smallest_by_oracle(2, f, 1, 9) == 1);
  assert_that(tools::kth_smallest_by_oracle(3, f, 1, 9) == 2);
  assert_that(tools::kth_smallest_by_oracle(4, f, 1, 9) == 3);
  assert_that(tools::kth_smallest_by_oracle(5, f, 1, 9) == 3);
  assert_that(tools::kth_smallest_by_oracle(6, f, 1, 9) == 4);
  assert_that(tools::kth_smallest_by_oracle(7, f, 1, 9) == 5);
  assert_that(tools::kth_smallest_by_oracle(8, f, 1, 9) == 5);
  assert_that(tools::kth_smallest_by_oracle(9, f, 1, 9) == 5);
  assert_that(tools::kth_smallest_by_oracle(10, f, 1, 9) == 6);
  assert_that(tools::kth_smallest_by_oracle(11, f, 1, 9) == 9);

  return 0;
}

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

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#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/kth_smallest_by_oracle.hpp"



#include <utility>
#line 1 "tools/detail/kth_largest_by_oracle.hpp"



#include <cassert>
#include <cmath>
#include <concepts>
#include <numeric>
#include <type_traits>
#include <tuple>
#line 11 "tools/detail/kth_largest_by_oracle.hpp"

namespace tools {
  namespace detail {
    namespace kth_largest_by_oracle {
      template <bool largest, typename F>
      requires std::regular_invocable<F, long long>
            && std::assignable_from<long long&, std::invoke_result_t<F, long long>>
      long long impl(const long long k, const F& f, const long long l, const long long r) {
        assert(1 <= k && k <= f(largest ? l : r));
        assert(l <= r);

        long long ok, ng;
        std::tie(ok, ng) = largest ? std::make_pair(l - 1, r + 1) : std::make_pair(r + 1, l - 1);
        while (std::abs(ng - ok) > 1) {
          const auto mid = std::midpoint(ok, ng);
          (std::cmp_greater_equal(f(mid), k) ? ok : ng) = mid;
        }
        return ok;
      }
    }
  }
}


#line 6 "tools/kth_smallest_by_oracle.hpp"

namespace tools {
  template <typename... Args>
  auto kth_smallest_by_oracle(Args&&... args) {
    return tools::detail::kth_largest_by_oracle::impl<false>(std::forward<Args>(args)...);
  }
}


#line 9 "tests/kth_smallest_by_oracle.test.cpp"

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

  const std::vector<int> S{1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9};
  const auto f = [&](const int x) {
    return std::distance(S.begin(), std::ranges::upper_bound(S, x));
  };

  assert_that(tools::kth_smallest_by_oracle(1, f, 1, 9) == 1);
  assert_that(tools::kth_smallest_by_oracle(2, f, 1, 9) == 1);
  assert_that(tools::kth_smallest_by_oracle(3, f, 1, 9) == 2);
  assert_that(tools::kth_smallest_by_oracle(4, f, 1, 9) == 3);
  assert_that(tools::kth_smallest_by_oracle(5, f, 1, 9) == 3);
  assert_that(tools::kth_smallest_by_oracle(6, f, 1, 9) == 4);
  assert_that(tools::kth_smallest_by_oracle(7, f, 1, 9) == 5);
  assert_that(tools::kth_smallest_by_oracle(8, f, 1, 9) == 5);
  assert_that(tools::kth_smallest_by_oracle(9, f, 1, 9) == 5);
  assert_that(tools::kth_smallest_by_oracle(10, f, 1, 9) == 6);
  assert_that(tools::kth_smallest_by_oracle(11, f, 1, 9) == 9);

  return 0;
}