Competitive Programming Solutions

arc109_b - Log

28 Nov 2020 — Tags: binary_search — URL

Pick the log of size n + 1 and maximize the amount of logs from [1 … m] that can be cut from n + 1.

\[argmax_{m}((n + 1 - \sum_{i = 1}^{m} i) \geq 0)\]

Time complexity: $O(\log{n})$

Memory complexity: $O(1)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using predicate = function<bool(ll)>;
ll n;
inline bool ok(ll m) { return (2 * (n + 1)) / m >= m + 1; }
ll bs(ll l, ll r, predicate p)
{
    while (l < r)
    {
        ll m = l + (r - l + 1) / 2;
        if (p(m))
            l = m;
        else
            r = m - 1;
    }
    return l;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> n;
    auto ans = bs(1, n, ok);
    cout << n - ans + 1 << endl;
    return 0;
}

Related posts