cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub naskya/cp-library-cpp

:heavy_check_mark: test/search/binary_search/1.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_B"
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

#include "../../../include/search/binary_search.hpp"

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

  int n;
  std::cin >> n;

  std::vector<int> S(n + 2);
  std::copy_n(std::istream_iterator<int>(std::cin), n, std::begin(S) + 1);

  S.front() = -2000000000;
  S.back()  = 2000000000;

  int q;
  std::cin >> q;

  int t;
  const auto lower_bound = [&](const int idx) -> bool { return S[idx] <= t; };

  long long res = 0;

  while (q--) {
    std::cin >> t;
    const int idx = lib::binary_search(0, n + 1, lower_bound);
    res += (S[idx] == t);
  }

  std::cout << res << "\n";
}
#line 1 "test/search/binary_search/1.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_B"
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

#line 1 "include/search/binary_search.hpp"

//! @file binary_search.hpp

#ifndef CP_LIBRARY_BINARY_SEARCH_HPP
#define CP_LIBRARY_BINARY_SEARCH_HPP

#include <cassert>
#include <type_traits>
#include <utility>

#ifndef CP_LIBRARY_ASSERT
//! @brief Assert macro
#  define CP_LIBRARY_ASSERT(...) assert(__VA_ARGS__)
#  define CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

namespace lib {

//! @brief Find the minimum or maximum value that satisfies the condition.
//! @tparam Tp Return type (deduced from parameters)
//! @tparam Func callable type (function reference, class with operator(), ...)
//! @param ok Initial value for which the condition is satisfied
//! @param ng Initial value for which the condition is not satisfied
//! @param f Callable object that takes 1 parameter of Tp and returns bool indicating if the condition is satisfied
//! @param diff Difference (end condition of binary search). 1 for integers, small value (e.g. 1e-9) for real numbers
//! @return minimum value (if ok < ng) or maximum value (if ok > ng)
//! @note One and only one boundary value between ok and ng must exist.
//! @note Time complexity: O(log(|ok - ng|))
template <typename Tp, typename Func>
[[nodiscard]] Tp binary_search(Tp ok, Tp ng, const Func& f, const Tp diff = 1) {
  static_assert(std::is_same_v<decltype(std::declval<Func>()(std::declval<Tp>())), bool>);
  CP_LIBRARY_ASSERT(f(ok));
  CP_LIBRARY_ASSERT(!f(ng));

  if (ok < ng)
    while (ng - ok > diff) {
      const Tp mid       = ok + (ng - ok) / 2;
      (f(mid) ? ok : ng) = mid;
    }
  else
    while (ok - ng > diff) {
      const Tp mid       = ng + (ok - ng) / 2;
      (f(mid) ? ok : ng) = mid;
    }

  return ok;
}

}  // namespace lib

#ifdef CP_LIBRARY_ASSERT_NOT_DEFINED
#  undef CP_LIBRARY_ASSERT
#  undef CP_LIBRARY_ASSERT_NOT_DEFINED
#endif

#endif  // CP_LIBRARY_BINARY_SEARCH_HPP
#line 8 "test/search/binary_search/1.test.cpp"

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

  int n;
  std::cin >> n;

  std::vector<int> S(n + 2);
  std::copy_n(std::istream_iterator<int>(std::cin), n, std::begin(S) + 1);

  S.front() = -2000000000;
  S.back()  = 2000000000;

  int q;
  std::cin >> q;

  int t;
  const auto lower_bound = [&](const int idx) -> bool { return S[idx] <= t; };

  long long res = 0;

  while (q--) {
    std::cin >> t;
    const int idx = lib::binary_search(0, n + 1, lower_bound);
    res += (S[idx] == t);
  }

  std::cout << res << "\n";
}
Back to top page