Problem:


Search II

You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.

Input

In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.

Output

Print C in a line.

Constraints

Elements in S is sorted in ascending order

n ≤ 100000

 q ≤ 50000 

0 ≤ an element in S ≤ 109

0 ≤ an element in T ≤ 109

Sample Input 1

5
1 2 3 4 5
3
3 4 1

Sample Output 1

3

Sample Input 2

3
1 2 3
1
5

Sample Output 2

0

Sample Input 3

5
1 1 2 2 3
2
1 2

Sample Output 3

2

Notes

Template in C
-->



Sample input:
5
1 2 3 4 5
3
3 4 1


Sample output:
3

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools

input = sys.stdin.readline
_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)


def solve():

    N = iip()
    S = iip()
    M = iip()
    T = iip()

    S.sort()

    ans = 0
    for i in T:
        if index_sorted(S, i) is not False:
            ans += 1
    print(ans)






#####################################################ライブラリ集ここから


def kiriage_warizan(a, b):
    return -(-a//b)


def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iipt(l, listed=True, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0] # 間違って要素１個のタプルを渡されても受け取る
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()

def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N-1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left"): # 関数を二分探索
    l = left
    r = right
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if func(x) == target:
            return x
        elif func(x) > target:
            r = x
        else:
            l = x

    if side == "left" or func(x) == target:
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r-l > 1:
        x = (l+r)//2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                #for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))


#Binary Search
def BinarySearch(A,n, key):
    left  = -1
    right = n
    i = 0
    while left < right:

        mid   = (left + right) // 2
        if A[mid] == key:
            return True
        elif key > A[mid]:
            left = mid + 1
        else:
            right = mid
    return False

cnt = 0
for i in range(q):
    if BinarySearch(S, n, T[i]):
        cnt = cnt+1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
C = 0

for i in range(q):
	s_idx = 0
	g_idx = n
	while s_idx != g_idx:
		idx = (s_idx + g_idx) // 2
		if S[idx] == T[i]:
			C += 1
			break
		elif S[idx] < T[i]:
			s_idx = idx + 1
		elif S[idx] > T[i]:
			g_idx = idx

print(C)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

from bisect import bisect_left
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    n = int(readline())
    S = [int(i) for i in readline().split()]
    q = int(readline())
    T = [int(i) for i in readline().split()]
    
    ans = 0
    for t in T:
        x = bisect_left(S, t)
        if x == n:
            if S[-1] == t:
                ans += 1
        else:
            if S[x] == t:
                ans += 1
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]

ans = 0
for i in t:
    left = 0
    right = n-1
    mid = 0
    while left <= right:
        mid = (left + right)//2
        if s[mid] == i:
            ans += 1
            break
        elif s[mid] < i:
            left = mid+1
        else:
            right = mid-1
 
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect


# from operator import mul

# sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n = int(input())
data = getInputIntList()
t = int(input())
candidate = getInputIntList()

D = set(data)

ans = 0
for c in candidate:
    if c in D:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
import bisect as bs

def resolve():
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))

    ans = 0
    for t in T:
        i = bs.bisect_left(S, t)
        if i<len(S) and t==S[i]:
            ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right  # return index

def search(t, i):
    ix = bisect_right(t, i)
    if t[ix-1] != i:
        return False
    return True

n = int(input())
s = list(set(list(map(int, input().split()))))
q = int(input())
t = sorted(list(set(list(map(int, input().split())))))

ans = 0
for i in s:
    ans += search(t, i)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = 0
for i in T:
    if i == S[-1] or i == S[0]:
        ans += 1
    else:
        left = 0
        right = n-1
        while right-left > 1:
            mid = (left+right)//2
            if S[mid] == i:
                ans += 1
                break
            elif S[mid] < i:
                left = mid
            else:
                right = mid

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))
ans = 0
def binary_search(S,key):  #昇順リストSからkeyを探す。
    n = len(S)             #存在したらindex,なかったら-1を返す
    left  = 0
    right = n
    while left < right:
        mid = (left+right) // 2
        if S[mid] == key:
            return mid
        elif S[mid] > key:
            right = mid
        else:
            left = mid + 1
    return -1
for i in range(q):
    if binary_search(S,T[i]) != -1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
S = list(map(int, input().split()))
p = int(input())
T = list(map(int, input().split()))

ans = 0
def sh(num):
    ind = bisect_left(S, num)
    return S[ind] == num

for t in T:
    if sh(t):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

def main():
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))

    count = 0
    for t in T:
        i = bisect_left(S, t)
        if i != len(S) and S[i] == t:
            count += 1
    print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

count = 0
for t in T:
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if S[mid] == t:
            count += 1
            break
        elif S[mid] > t:
            right = mid
        else:
            left = mid + 1
print(count)

Submission status: Accepted

Solution code:
def binary_search(lst, x):
    left=0
    right=len(lst)
    while left<right:
        m=(left+right)//2
        if lst[m]==x:
            return True
        elif x<lst[m]:
            right=m
        else:
            left=m+1
    return False

def main():
    n=int(input())
    S=list(map(int,input().split()))
    q=int(input())
    T=list(map(int,input().split()))
    ans=0
    for t in T:
        if binary_search(S,t):
            ans+=1
    print(ans)

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]

ans = 0
for ti in t:
    idx = bisect_left(s, ti)
    if s[idx] == ti:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))

    result = 0
    for t in T:
        l = 0
        r = n - 1
        while l <= r:

            # print('t {} l {} r {}'.format(t, l, r))
            c = (l + r) // 2
            if t < S[c]:
                r = c - 1
                continue
            elif t == S[c]:
                result += 1
                break
            elif S[c] < t:
                l = c + 1
                continue
            raise Exception

    print(result)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))
# tをソートしてしたから見て行ってもいいが、二分探索でとく
def binary_search(search,list_):
  # search がlist_ の中にあるかを判定する
  l = 0
  r = len(list_)
  while r-l > 1:
    m = (l+r)//2
    if list_[m] > search: r = m
    elif list_[m] < search: l = m
    else:return m
  if r-l == 1:
    if search == list_[l]: return 0
    else: return -1
ans = 0
for i in t:
  if binary_search(i,s) >= 0: 
    ans += 1
    #print(i,s)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))
cnt = 0

def binary_search(l,num):
    left = 0
    right = n
    flag = 0
    while left < right:
        mid = (left + right)//2
        if l[mid] == num:
            flag = 1
            return(flag)
        elif l[mid] > num:
            right = mid
        else:
            left = mid + 1
    return(flag)
    
for i in T:
    cnt += binary_search(S,i)
print(cnt)

Submission status: Accepted

Solution code:
# Binary search 二分検索
def binarySearch(A, n, k):
    left = 0
    right = n
    while left < right:
        mid = int((left + right) / 2)
        if A[mid] == k:
            return mid
        elif A[mid] > k:
            right = mid
        elif A[mid] < k:
            left = mid + 1
    return -1


n = int(input())
S = [int(i) for i in input().split()]
q = int(input())
T = [int(i) for i in input().split()]
C = 0
for t in T:
    if binarySearch(S, n, t) != -1:
        C += 1
print(C)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

def search(ary, target):
    left = 0
    right = len(ary)
    while (left < right):
        idx = (left+right)//2
        if ary[idx] == target:
            return True
        if ary[idx] < target:
            left = idx + 1
        elif ary[idx] > target:
            right = idx
        else:
            return False
    return False

result = 0;
for i in t:
    if search(s, i):
        result += 1
print(result)

Submission status: Accepted

Solution code:
import math

def bs(lis,target): 

    result = -1
    left = 0
    right = len(lis) - 1

    while left <= right:
        center = (left + right)//2
        if lis[center] == target:
            result = center
            break
        elif lis[center] < target:
            left = center + 1
        elif lis[center] > target:
            right = center - 1

    return result

n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))

ans = 0
for i in t:
    if bs(s,i) != -1:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))

c=0
for j in range(q):
	l=-1
	r=n
	while l+1<r:
		m=(l+r)//2
		if S[m]==T[j]:
			c+=1
			break
		elif S[m]<T[j]:
			l=m
		else:
			r=m
print(c)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = list(map(int, input().split()))


ans = 0
for b in B:
    r = bisect.bisect_right(A, b)
    l = bisect.bisect_left(A, b)
    if r != l:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

import bisect

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

counter = 0

for t in T:
    a = bisect.bisect_left(S, t)
    if a < n:
        if S[a] == t:
            counter += 1

print(counter)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split(' ')))
S.sort()
q = int(input())
T = list(map(int, input().split(' ')))

def binarySearch(key):
  left = 0
  right = n - 1
  mid = (left + right) // 2
  while S[mid] != key:
    if left == right:
      return 0
    if S[mid] > key:
      right = mid
    elif S[mid] < key:
      left = mid + 1
    mid = (left + right) // 2
  return 1
  
count = 0
for t in T:
  count += binarySearch(t)
print(count)

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    a = list(map(int,input().split()))
    m = int(input())
    b = list(map(int,input().split()))
    res = 0
    for i in range(m):
        l = 0
        r = n
        while l<r:
            mid = int((l+r)/2)
            if b[i]==a[mid]:
                res+=1
                break
            if b[i]>a[mid]:l = mid+1
            else          :r = mid
    print (res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bisect


def inpl():
    return list(map(int, input().split()))


n = int(input())
S = inpl()
q = int(input())
T = inpl()

S.sort()
S.append(10**11)

# print(S, bisect(S, T[0]))
print(sum(1 for t in T if S[bisect(S, t)] == t))

Submission status: Accepted

Solution code:
n=int(input())
s=list(map(int,input().split()))
q=int(input())
t=list(map(int,input().split()))

def bin(a):
    ok=n-1#okのところは範囲に含める必要がある
    ng=-1#ngは範囲外に置く

    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if s[mid]>=a:
            ok=mid
        else:
            ng=mid
    if s[ok]==a:return 1
    else:return 0

ans=0
for i in t:
    ans+=bin(i)
print(ans)

Submission status: Accepted

Solution code:
import bisect
N=int(input())
S=list(map(int,input().split()))
Q=int(input())
T=list(map(int,input().split()))
X=0
P=0
for i in range(Q):
  X=bisect.bisect_left(S,T[i])
  if S[X]==T[i]:
    P=P+1
print(P)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# ALDS1_4_B_BinarySearch

import sys

def input_lines():
    return sys.stdin.readlines()

def binary_search(l, v):    
    low = 0
    high = len(l) - 1
    while low <= high:
        mid = (low + high) // 2
        if l[mid] == v:
            return mid
        elif l[mid] < v:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def main():
    lines = input_lines()
    s = sorted(set(map(int, lines[1].split())))
    t = sorted(map(int, lines[3].split()))
    
    count = 0
    for v in t:
        res = binary_search(s, v)
        if res != -1:
            count += 1
            s = s[res + 1:]
    print(count)
    
main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
cnt = 0
for i in range(q):
    idx = bisect_left(S, T[i])
    if idx == n:
        continue
    if S[idx] == T[i]:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = map(int, input().split())
a = 0
for t in T:
  if S[bisect_left(S, t)]==t:
    a += 1
print(a)

Submission status: Accepted

Solution code:
# import numpy as np
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))


def binary_search(A, key):
    n = len(A)
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False


count = 0
for i in range(q):
    key = T[i]
    # binary search
    if binary_search(S, key):
        count += 1
print(count)

Submission status: Accepted

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
# import sys

# sys.setrecursionlimit(10 ** 5 + 10)


# input = sys.stdin.readline

def resolve():
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))

    ans = 0

    for i in T:
        pl = 0
        pr = n - 1

        while pl <= pr:
            pc = (pl + pr) // 2
            if S[pc] == i:
                ans += 1
                break
            elif i < S[pc]:
                pr = pc - 1
            else:
                pl = pc + 1

    print(ans)


resolve()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
t=int(input())
b=list(map(int,input().split()))
a=sorted(a)

import bisect
cnt=0
for i in b:
    x=bisect.bisect_left(a,i)
    if x!=n and i==a[x]:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import math
N = int(input())
S = list(map(int,input().split()))

Q = int(input())
T = list(map(int,input().split()))


ans = 0
for i in range(Q):
    left = 0
    right = N-1
    key = T[i]
    
    while left <= right:
        mid =(left+right)//2

        if S[mid] == key:
            ans += 1
            break
        elif S[mid] < key:
            left = mid+1

        else:
            right = mid-1
        
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
cnt = 0

def find_idx(l, x):
    i = bisect_left(l, x)
    if i != len(l) and l[i] == x:
        return 1
    else:
        return 0

for i in T:
    cnt += find_idx(S, i)

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = 0

# 再帰で書くと遅い

# def bin_search(li_sorted, val):
#     global ans
#     m = len(li_sorted)
#     l = int(m / 2)
#     if val == li_sorted[l]:
#         ans += 1
#     elif m > 1:
#         li_left = li_sorted[:l]
#         li_right = li_sorted[l:]
#         bin_search(li_left, val)
#         bin_search(li_right, val)


# for i in range(q):
#     bin_search(S, T[i])

for i in range(q):
    val = T[i]
    left = 0
    right = n
    while left < right:
        mid = (left + right)//2
        if S[mid] == val:
            ans += 1
            break
        elif S[mid] < val:
            left = mid + 1
        else:
            right = mid

print(ans)

Submission status: Accepted

Solution code:
def findNum(array, target):
    n = len(array)
    l = -1
    r = n  # bigger than target
    while l + 1 < r:
        m = (l + r) // 2
        if array[m] == target:
            return True
        elif array[m] < target:
            l = m
        else:
            r = m

    if r < n and array[r] == target:
        return True
    else:
        return False


n = int(input())
array = list(map(int, input().split()))

q = int(input())
m = list(map(int, input().split()))

count = 0
for i in range(q):
    if findNum(array, m[i]):
        count += 1

print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left
n = int(input())
S = [int(x) for x in input().split()]
q = int(input())
T = [int(x) for x in input().split()]
ans = 0
for t in T:
    idx = bisect_left(S, t)
    if idx != n and S[idx] == t:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    S=list(map(int,input().split()))
    Q=int(input())
    T=list(map(int,input().split()))
    ans=0
    for x in T:
        ans+=bool(bisect_right(S,x)-bisect_left(S,x))
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
s = na()
q = ni()
t = na()
ans = 0
for x in t:
    d = bisect.bisect_right(s, x) - bisect.bisect_left(s, x)
    if d != 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

count = 0
for t in T:
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if t == S[mid]:
            count += 1
            break
        elif t < S[mid]:
            right = mid
        else:
            left = mid + 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
S = list(map(int,input().split()))
q = int(input())
T = map(int,input().split())
ret = 0
for t in T:
  ok = 0
  ng = n
  while ng-ok > 1:
    mid = (ok+ng)//2
    if t < S[mid]:
      ng = mid
    else:
      ok = mid
  if S[ok]==t:
    ret += 1
print(ret)

Submission status: Accepted

Solution code:
N=int(input())
S=list(map(int,input().split()))
Q=int(input())
T=list(map(int,input().split()))

cnt=0
for t in T:
    left=0
    right=N
    while left < right:
        mid=round((left+right-0.0001)/2)
#         print(t,mid,S[mid],left,right)
        if S[mid] == t:
            cnt+=1
            break
        elif S[mid] > t:
            right = mid
        elif S[mid] < t:
            left = mid+1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
# print(n, S, q, T)

def binary_search(arr, x):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = int((left + right) / 2)
        if arr[mid] < x:
            left = mid + 1
        elif arr[mid] > x:
            right = mid - 1
        else:
            return mid
    return -1

S.sort()
count = 0
for i in range(q):
    if binary_search(S, T[i]) != -1:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
q = int(input())
a = list(map(int, input().split()))

def b_search(b, x, l, r):
    while l+1<r:
        m = (l+r)//2
        if b[m]<x:
            l = m
        else:
            r = m
    
    if b[r]==x:
        return True
    else:
        return False
    
s.sort()
cnt = 0
for ai in a:
    if b_search(s, ai, -1, n-1):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n = input()
S = list(map(int, input().split()))
q = input()
T = list(map(int, input().split()))

def binarySearch(key, A):
    n = len(A)
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return False

count = 0
for elem in T:
    if binarySearch(elem, S):
        count = count + 1
print(count)

Submission status: Accepted

Solution code:
from math import floor

def binary_search(A, key):
    left = 0
    right = len(A)

    while left < right:
        mid = (left + right) // 2
        # print("left, right, mid, key, A[mid]:", left, right, mid, key, A[mid])
        if A[mid] == key:
            return mid
        elif A[mid] > key:
            right = mid
        else:
            left = mid + 1
    return None



def main():
    n = int(input())
    S = list(map(int, input().split((' '))))
    q = int(input())
    T = list(map(int, input().split((' '))))

    ans = 0

    for key in T:
        # print("key:", key)
        if binary_search(S, key) is not None:
            ans += 1

    print(ans)

            

main()

Submission status: Accepted

Solution code:
def binary_search(t,S):
  start = 0
  end = len(S)-1
  flag = False
  while start <= end:
    mid = (start + end) //2
    if t == S[mid]:
      flag = True
      break
    elif t < S[mid]:
      end = mid -1
    else:
      start = mid + 1
  if flag:
    return True
  else:
    return False

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

ans = 0
for t in T:
  if binary_search(t, S):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))

cnt = 0
for t in T:
    head = 0
    tail = n - 1
    while head <= tail:
        i = (head + tail) // 2
        if S[i] == t:
            cnt += 1
            break
        elif S[i] < t:
            head = i + 1
        else:
            tail = i - 1

print(cnt)