test/aoj/alds1_4_b.test.cpp

View this file on GitHub
Last update: 2022-12-24 14:04:00+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_4_B

Depends on

src/search/binary_search.hpp

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "../../src/search/binary_search.hpp"

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(q);
  for (int i = 0; i < q; ++i) {
    cin >> T[i];
  }

  int ans = 0;
  for (int i = 0; i < q; ++i) {
    int lower = bin_search<int>(-1, n, [&](int idx) { return S[idx] >= T[i]; });
    int upper = bin_search<int>(n, -1, [&](int idx) { return S[idx] <= T[i]; });
    if (lower <= upper) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/search/binary_search.hpp"

#line 4 "src/search/binary_search.hpp"
using namespace std;

template <typename T> T bin_search(T ng, T ok, function<bool(T)> is_ok) {
  while (abs(ok - ng) > 1) {
    T mid = (ok + ng) / 2;

    if (is_ok(mid)) {
      ok = mid;
    } else {
      ng = mid;
    }
  }
  return ok;
}
#line 8 "test/aoj/alds1_4_b.test.cpp"

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(q);
  for (int i = 0; i < q; ++i) {
    cin >> T[i];
  }

  int ans = 0;
  for (int i = 0; i < q; ++i) {
    int lower = bin_search<int>(-1, n, [&](int idx) { return S[idx] >= T[i]; });
    int upper = bin_search<int>(n, -1, [&](int idx) { return S[idx] <= T[i]; });
    if (lower <= upper) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}