ALDS1_4_B

T[i]がSの中に含まれているかを二分探索する。

二分探索は関数化すると実装しやすい。

問題とは関係ないけど、macを購入してから初めてのAC

自分の持ってるwindows機より軽くて持ち運びやすいmacbook airで競プロできるのは勉強時間増えるのでGOOD

#include<bits/stdc++.h>

using namespace std;

int n, s[100001], q;

bool solve(int a){

int ok = 0;

int ng = n;

while(abs(ok-ng)>1){

int mid = (ok+ng)/2;

if(s[mid] <= a) ok = mid;

else ng = mid;

//cout << mid << endl;

}

return s[ok] == a;

}

int main(){

cin >> n;

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

sort(s, s+n);

cin >> q;

int cnt = 0;

for(int i=0;i<q;i++){

int a;

cin >> a;

if(solve(a)) cnt++;

}

cout << cnt << endl;

}