other/exp_search.hpp

• View this file on GitHub
• Last update: 2025-12-07 20:35:27+09:00
• Include: #include "other/exp_search.hpp"

Code

// find max true
template <typename F>
ll exp_search(F check, ll ok) {
  ll d = 1;
  while (check(ok + d)) {
    ok += d;
    d += d;
  }
  ll ng = ok + d;
  while (ok + 1 < ng) {
    ll x = (ok + ng) / 2;
    (check(x) ? ok : ng) = x;
  }
  return ok;
}

#line 1 "other/exp_search.hpp"
// find max true
template <typename F>
ll exp_search(F check, ll ok) {
  ll d = 1;
  while (check(ok + d)) {
    ok += d;
    d += d;
  }
  ll ng = ok + d;
  while (ok + 1 < ng) {
    ll x = (ok + ng) / 2;
    (check(x) ? ok : ng) = x;
  }
  return ok;
}

Back to top page