utils/binary_search.aoj.test.cpp

View this file on GitHub
Last update: 2021-08-30 04:35:37+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B"
#include "../utils/binary_search.hpp"
#include "../utils/binary_search_max.hpp"

#include <cassert>
#include <cstdint>
#include <iostream>
#include <vector>
#include "../utils/macros.hpp"
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> s(n);
    REP (i, n) {
        cin >> s[i];
    }

    int q; cin >> q;
    int64_t cnt = 0;
    while (q --) {
        int t_i; cin >> t_i;
        int l = binsearch(0, n, [&](int i) {
            return s[i] >= t_i;
        });
        cnt += (l < n and s[l] == t_i);

        int r = binsearch_max(0, n, [&](int i) {
            return s[i] <= t_i;
        });
        assert ((l < n and s[l] == t_i) == (l <= r));
    }

    cout << cnt << endl;
    return 0;
}

#line 1 "utils/binary_search.aoj.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B"
#line 2 "utils/binary_search.hpp"
#include <cassert>
#include <cstdint>

/**
 * @brief a binary search / 二分探索
 * @param[in] p  a monotone predicate defined on $[l, r)$
 * @return $\min \lbrace x \in [l, r) \mid p(x) \rbrace$, or r if it doesn't exist
 */
template <typename UnaryPredicate>
int64_t binsearch(int64_t l, int64_t r, UnaryPredicate p) {
    assert (l <= r);
    -- l;
    while (r - l > 1) {
        int64_t m = l + (r - l) / 2;
        (p(m) ? r : l) = m;
    }
    return r;
}
#line 4 "utils/binary_search_max.hpp"

/**
 * @return $\max \lbrace x \in (l, r] \mid p(x) \rbrace$, or l if it doesn't exist
 */
template <typename UnaryPredicate>
int64_t binsearch_max(int64_t l, int64_t r, UnaryPredicate p) {
    assert (l <= r);
    ++ r;
    while (r - l > 1) {
        int64_t m = l + (r - l) / 2;
        (p(m) ? l : r) = m;
    }
    return l;
}
#line 4 "utils/binary_search.aoj.test.cpp"

#line 7 "utils/binary_search.aoj.test.cpp"
#include <iostream>
#include <vector>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 10 "utils/binary_search.aoj.test.cpp"
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> s(n);
    REP (i, n) {
        cin >> s[i];
    }

    int q; cin >> q;
    int64_t cnt = 0;
    while (q --) {
        int t_i; cin >> t_i;
        int l = binsearch(0, n, [&](int i) {
            return s[i] >= t_i;
        });
        cnt += (l < n and s[l] == t_i);

        int r = binsearch_max(0, n, [&](int i) {
            return s[i] <= t_i;
        });
        assert ((l < n and s[l] == t_i) == (l <= r));
    }

    cout << cnt << endl;
    return 0;
}