test/Bsearch.test.cpp

• View this file on GitHub
• Last update: 2021-03-24 15:18:21+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_6_C

Depends on

• Utility/Bsearch.cpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_6_C"
#include "./../Utility/Bsearch.cpp"
#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<int> a(n);
	for (int& i : a) cin >> i;
	int q;
	for (cin >> q; q--;) {
		int x;
		cin >> x;
		cout << Bsearch(0, n - 1, [&](int i) { return a[i] >= x; }).value_or(n) << '\n';
	}
}

#line 1 "test/Bsearch.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_6_C"
#line 2 "Utility/Bsearch.cpp"
#include <optional>
#include <type_traits>
#include <cassert>

template <class T, class F, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
std::optional<T> Bsearch(T left, T right, F f) {
	if (left > right || !f(right)) {
		return std::nullopt;
	} else if (f(left)) {
		return left;
	}
	while (right - left > 1) {
		T middle = (left + right) / 2;
		(f(middle) ? right : left) = middle;
	}
	assert(!f(left));
	assert(f(right));
	return right;
}
#line 3 "test/Bsearch.test.cpp"
#include <iostream>
#include <vector>
using namespace std;

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<int> a(n);
	for (int& i : a) cin >> i;
	int q;
	for (cin >> q; q--;) {
		int x;
		cin >> x;
		cout << Bsearch(0, n - 1, [&](int i) { return a[i] >= x; }).value_or(n) << '\n';
	}
}

Back to top page