verify/aoj-ALDS1_4_B-binary_search.test.cpp

View this file on GitHub
Last update: 2025-07-03 00:41:25+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_B

Depends on

algorithm/Others/binary_search.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_B"

#include <iostream>
#include <vector>

#include "../algorithm/Others/binary_search.hpp"

int main() {
    int n;
    std::cin >> n;

    std::vector<int> s(n);
    for(auto &elem : s) std::cin >> elem;

    int q;
    std::cin >> q;

    int ans = 0;
    while(q--) {
        int t;
        std::cin >> t;

        auto itr = algorithm::bisearch(0, n, [&](int i) -> bool {
            return s[i] < t;
        });

        if(itr < n and s[itr] == t) ++ans;
    }

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

#line 1 "verify/aoj-ALDS1_4_B-binary_search.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_B"

#include <iostream>
#include <vector>

#line 1 "algorithm/Others/binary_search.hpp"



#include <cassert>
#include <concepts>
#include <numeric>
#include <type_traits>

namespace algorithm {

template <std::integral Type, class Pred>
constexpr Type bisearch(Type ok, Type ng, Pred pred) {
    static_assert(std::is_invocable_r<bool, Pred, Type>::value);
    assert(ok <= ng);
    if(!pred(ok)) return ok;
    while(ng - ok > 1) {
        Type mid = std::midpoint(ok, ng);
        (pred(mid) ? ok : ng) = mid;
    }
    return ng;
}

template <std::floating_point Type, class Pred>
constexpr Type bisearch(Type ok, Type ng, Type eps, Pred pred) {
    static_assert(std::is_invocable_r<bool, Pred, Type>::value);
    assert(ok <= ng);
    if(!pred(ok)) return ok;
    while(ng - ok > eps) {
        Type mid = std::midpoint(ok, ng);
        (pred(mid) ? ok : ng) = mid;
    }
    return ng;
}

}  // namespace algorithm


#line 7 "verify/aoj-ALDS1_4_B-binary_search.test.cpp"

int main() {
    int n;
    std::cin >> n;

    std::vector<int> s(n);
    for(auto &elem : s) std::cin >> elem;

    int q;
    std::cin >> q;

    int ans = 0;
    while(q--) {
        int t;
        std::cin >> t;

        auto itr = algorithm::bisearch(0, n, [&](int i) -> bool {
            return s[i] < t;
        });

        if(itr < n and s[itr] == t) ++ans;
    }

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