test/aoj/ALDS1_4_B.test.cpp

View this file on GitHub
Last update: 2021-02-09 21:26:13+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B

Depends on

src/bisearch.hpp

Code

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

#include "../../src/bisearch.hpp"

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;
using lint = long long;

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int n;
    cin >> n;
    vector<int> S(n);
    for (int i = 0; i < n; i++) cin >> S[i];

    int q;
    cin >> q;
    vector<int> T(n);
    for (int i = 0; i < q; i++) cin >> T[i];

    int ans = 0;
    for (int i = 0; i < q; i++) {
        auto f = [&](int index) { return index < n && S[index] <= T[i]; };
        int index = bisearch(0, n, f);
        ans += S[index] == T[i];
    }
    
    cout << ans << '\n';

    return 0;
}

#line 1 "test/aoj/ALDS1_4_B.test.cpp"

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

#line 2 "src/bisearch.hpp"

#include <cmath>

using namespace std;

template<class T, class F>
T bisearch(T OK, T NG, F f) {
    T ok = OK;
    T ng = NG;

    while (abs(ok - ng) > 1) {
        auto mid = (ok + ng) / 2;

        if (f(mid)) ok = mid;
        else ng = mid;
    }

    return ok;
}
#line 5 "test/aoj/ALDS1_4_B.test.cpp"

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;
using lint = long long;

struct init {
    init() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
    }
} init_;

int main() {

    int n;
    cin >> n;
    vector<int> S(n);
    for (int i = 0; i < n; i++) cin >> S[i];

    int q;
    cin >> q;
    vector<int> T(n);
    for (int i = 0; i < q; i++) cin >> T[i];

    int ans = 0;
    for (int i = 0; i < q; i++) {
        auto f = [&](int index) { return index < n && S[index] <= T[i]; };
        int index = bisearch(0, n, f);
        ans += S[index] == T[i];
    }
    
    cout << ans << '\n';

    return 0;
}