test/binary_search.test.cpp

View this file on GitHub
Last update: 2024-06-15 20:04:59+09:00
Problem: https://atcoder.jp/contests/typical90/tasks/typical90_a
Link: View error logs on GitHub Actions

Depends on

algo/binary_search.hpp

Code

#define PROBLEM "https://atcoder.jp/contests/typical90/tasks/typical90_a"
#include <bits/stdc++.h>
#include "../algo/binary_search.hpp"
using namespace std;

int main() {
    int n, l, k;
    cin >> n >> l >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << find_border<int>(0, 1e9, [&](int x) {
        int cnt = 0;
        int last = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] - last >= x) {
                cnt++;
                last = a[i];
            }
        }
        cnt += l - last >= x;
        return cnt >= k + 1;
    }) << endl;
}

#line 1 "test/binary_search.test.cpp"
#define PROBLEM "https://atcoder.jp/contests/typical90/tasks/typical90_a"
#include <bits/stdc++.h>
#line 2 "algo/binary_search.hpp"

// binary search, finds the border of determ
template <typename T = long long, typename F>
T find_border(T ok, T ng, const F determ) {
    while (abs(ok - ng) > 1) {
        T mid = (ok + ng) / 2;
        if (determ(mid)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}
#line 4 "test/binary_search.test.cpp"
using namespace std;

int main() {
    int n, l, k;
    cin >> n >> l >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cout << find_border<int>(0, 1e9, [&](int x) {
        int cnt = 0;
        int last = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] - last >= x) {
                cnt++;
                last = a[i];
            }
        }
        cnt += l - last >= x;
        return cnt >= k + 1;
    }) << endl;
}