Test/Algorithms/BinarySearch_int.test.cpp

• View this file on GitHub
• Last update: 2024-12-27 17:36:05+09:00
• Problem: https://yukicoder.me/problems/no/1882

Depends on

• Library/Algorithms/BinarySearch.hpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/1882"

#include <algorithm>

#include <iostream>

#include <ranges>

#include <vector>


// begin:tag includes

#include "./../../Library/Algorithms/BinarySearch.hpp"

// end:tag includes


using ll = long long;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  ll n, x;
  std::cin >> n >> x;
  std::vector<ll> a(n);
  for (int i = 0; i < n; ++i) { std::cin >> a[i]; }
  std::ranges::sort(a);

  ll ans = 0;
  for (const auto& val : a) {
    auto idx = mtd::binarySearch<>(
        n, -1, [&](ll mid) { return val * a[mid] >= (x << 1); });
    ans += n - idx;
  }

  std::cout << ans << std::endl;
}

#line 1 "Test/Algorithms/BinarySearch_int.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1882"

#include <algorithm>

#include <iostream>

#include <ranges>

#include <vector>


// begin:tag includes

#line 2 "Library/Algorithms/BinarySearch.hpp"

#include <concepts>

#include <numeric>

#line 6 "Library/Algorithms/BinarySearch.hpp"
#include <type_traits>


namespace mtd {

  template <class Lambda>
  auto binarySearch(double ok, double ng, int rep, const Lambda& is_ok) {
    for ([[maybe_unused]] auto _ : std::views::iota(0, rep)) {
      double mid = (ok + ng) / 2.0;
      (is_ok(mid) ? ok : ng) = mid;
    }
    return ok;
  }

  template <class Lambda, std::integral T1, std::integral T2>
  auto binarySearch(T1 ok_, T2 ng_, const Lambda& is_ok) {
    using T = std::common_type_t<T1, T2>;
    T ok = ok_, ng = ng_;
    while (std::abs(ok - ng) > 1) {
      T mid = (ok + ng) >> 1;
      (is_ok(mid) ? ok : ng) = mid;
    }
    return ok;
  }

}  // namespace mtd

#line 10 "Test/Algorithms/BinarySearch_int.test.cpp"
// end:tag includes


using ll = long long;

signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);

  ll n, x;
  std::cin >> n >> x;
  std::vector<ll> a(n);
  for (int i = 0; i < n; ++i) { std::cin >> a[i]; }
  std::ranges::sort(a);

  ll ans = 0;
  for (const auto& val : a) {
    auto idx = mtd::binarySearch<>(
        n, -1, [&](ll mid) { return val * a[mid] >= (x << 1); });
    ans += n - idx;
  }

  std::cout << ans << std::endl;
}

Back to top page