Test/Algorithms/BinarySearch_int_rev.test.cpp

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

Depends on

Library/Algorithms/BinarySearch.hpp

Code

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

#include <iostream>

#include <vector>


// begin:tag includes

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

// end:tag includes


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

  std::vector<int> a(3);
  for (int i = 0; i < 3; ++i) { std::cin >> a[i]; }

  auto ans = mtd::binarySearch(0, static_cast<int>(1e9), [&](int mid) {
    int d = 0;
    for (auto x : a) {
      if (x >= mid) {
        d += ((x - mid) >> 1);
      } else {
        d -= mid - x;
      }
    }
    return d >= 0;
  });

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

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

#include <iostream>

#include <vector>


// begin:tag includes

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

#include <concepts>

#include <numeric>

#include <ranges>

#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 8 "Test/Algorithms/BinarySearch_int_rev.test.cpp"
// end:tag includes


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

  std::vector<int> a(3);
  for (int i = 0; i < 3; ++i) { std::cin >> a[i]; }

  auto ans = mtd::binarySearch(0, static_cast<int>(1e9), [&](int mid) {
    int d = 0;
    for (auto x : a) {
      if (x >= mid) {
        d += ((x - mid) >> 1);
      } else {
        d -= mid - x;
      }
    }
    return d >= 0;
  });

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