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:
n=int(input())
S=list(map(int,input().split(" ")))
q=int(input())
T=list(map(int,input().split(" ")))

def bs(A, key, left, right):
    if left > right:
        return -1
    else:
        mid=left+(right-left)//2
        #print(mid)
        if A[mid]>key:
            return bs(A, key, left,mid-1)
        elif A[mid]<key:
            return bs(A, key, mid+1,right)
        else:
            return mid
count=0
for i in T:
    if bs(S,i,0,n-1)!=-1:
        count+=1
print(count)

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 i in range(q):
  l = -1
  u = len(s)
  while (u - l > 1):
    x = (u + l) // 2
    if s[x] >= t[i]:
      u = x
    else:
      l = x
  if s[l] == t[i] or s[u] == t[i]:
    count += 1
print(count)

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 x in t:
	low,up = 0,n
	while up - low > 1:
		mid = (up + low) // 2
		if s[mid] <= x:
			low = mid
		else:
			up = mid
	ans += (x == s[low])
print(ans)

Submission status: Accepted

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

count=0
U0 = max(S)+1
for i in T:
    L=-1
    U=int(n)
    
    while(U-L>1):    
        if S[(L+U)//2]<=i:
            L=(L+U)//2
        else:
            U=(L+U)//2
    if S[L]==i:
        count+=1
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
def search(l, k): # 二分探索を関数化
    # 現在の探索位置の左右端を管理
    left = 0
    right = len(l)
    while left + 1 < right:
        now = (left + right) // 2
        # 見つかった場合Trueを返す
        if l[now] == k:
            return(True)
        # 現在の探索位置が検索するものより大きい場合左側を探索
        elif k >= l[now]:
            left = now
        # 現在の探索位置が検索するものより小さい場合右側を探索
        else:
            right = now
    # 見つからない場合Falseを返す
    return(False)
# 各種入力
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
# 解答の初期化
ans = 0
for i in T:
    # 見つかった場合Trueが返ってくるのでansに1を足す
    if search(S, i) == True:
        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()))
s = list(set(s))
n = len(s)
t.sort()
s.sort()
c = 0
for i in range(q):
    l = 0
    u = n - 1
    while u - l > 1:
        x = int((l + u) / 2)
        if t[i] > s[x]:
            l = x
        elif t[i] < s[x]:
            u = x
        else:
            break
    if t[i] == s[x]:
        c += 1
    elif t[i] == s[l]:
        c += 1
    elif u <= n - 1:
        if t[i] == s[u]:
            c += 1
print(int(c))

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 t in T:
    L,U=-1,N
    while U-L>1:
        mid=(L+U)//2
        if S[mid]>=t:
            U=mid
        else:
            L=mid
    if S[U]==t:
        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()))
ans=0
for t in T:
    num_l=0
    num_r=n-1
    if not S[0]<= t <=S[-1]:
        continue
    while (num_r-num_l)>1:
        num_m=(num_r-num_l)//2+num_l
        if t>S[num_m]:
            num_l=num_m
        elif t<S[num_m]:
            num_r=num_m
        if t in [S[num_l],S[num_m],S[num_r]]:
            ans+=1
            break
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 ti in t:
    l = -1
    u = n
    while u - l > 1:
        m = (u + l) // 2
        if s[m] <= ti:
            if s[m] == ti:
                c += 1
                break
            l = m
        else:
            u = m
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 bisearch(t):
    L = -1
    U = n
    while U-L >1:
        x = (L+U)//2
        if S[x] > t:
            U = x
        elif S[x] < t:
            L =x
        else:
            return True
    return False
ans = 0
for t in T:
    if bisearch(t):
        ans += 1

print(ans)

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()]
c = 0
for t in T:#L<t,U>=t
    L = -1
    U = n
    while U - L > 1:
        x = (L+U)//2
        if S[x] >= t:
            U = x
        else:
            L = x
    if S[U]==t:
        c+=1
print(c)

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()))

ans = 0
for i in range(q):
    l = 0
    r = n
    while r - l > 1:
        m = (r + l) // 2
        if S[m] >= T[i]:
            r = m
        else:
            l = m
    
    if l < n and S[l] == T[i]:
        ans += 1
    elif r < n and S[r] == T[i]:
        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 i in range(q):
    l=0
    r=n-1
    while l<=r:
        mid = (l+r)//2 
        guess = S[mid]
        if guess == T[i]:
            cnt=cnt+1
            break
        if guess > T[i]:
            r=mid-1
        if guess < T[i]:
            l=mid+1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
s = set([int(x) for x in input().split()])
q = int(input())
t = [int(x) for x in input().split()]
ans = 0
for x in t:
  if x in s:
    ans  = ans + 1

print(ans)

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()]

count=0

for i in range(q):
    left=0
    right=n
    while left <= right:
        center=int((left+right)/2)
        if S[center] > T[i]:
            right=center-1
        elif S[center] < T[i]:
            left=center+1
        elif S[center]==T[i]:
            count+=1
            break

print(count)

Submission status: Accepted

Solution code:
from collections import deque

S = []
T = []

n = int(input())

S = [int(n) for n in input().split()]

q = int(input())

T = [int(q) for q in input().split()]

def binarySearch(key):
    left = 0
    right = n
    while left < right:
        mid = int((left + right) / 2)
        if S[mid] == key:
            return mid
        elif key < S[mid]:
            right = mid
        else: left = mid + 1
    return -1


cnt = 0

S.sort()
T.sort()
prev = -1

while len(T) > 0:
    key = T.pop()

    if key != prev and binarySearch(key) > 0:
        cnt += 1
    prev = key

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()))
cnt=0

for i in range(q):
    l=0
    r=n
    while l<r:
        m=int((l+r)/2)
        if s[m]==t[i]:
            cnt+=1
            break
        elif t[i]<s[m]:
            r=m
        else:
            l=m+1
print(cnt)

Submission status: Accepted

Solution code:
import math
def search(s,t):
    cnt=0
    s.sort()
    t.sort()
    for i in t:
        first=0
        last=len(s)
        mid=0
        while first<last:
            mid=(first+last)//2
            if s[mid] == i:
                cnt=cnt+1
                break
            elif s[mid]>i:
                last=mid
            else:
                first=mid+1
    return cnt
n=int(input())
s=list(map(int,input().split()))
q=int(input())
t=list(map(int,input().split()))
print(search(s,t))

Submission status: Accepted

Solution code:
def bi(s, a, l, r):
    if l > r:
        return 0
    
    m = (l + r) // 2
    if s[m] == a:
        return 1
    elif s[m] > a:
        return bi(s, a, l, m-1)
    elif s[m] < a:
        return bi(s, a, m+1, r)
    
n1 = int(input())
s = list(map(int, input().split()))
n2 = int(input())
t = list(map(int, input().split()))

s.sort()

ans = 0
for ti in t:
    ans += bi(s, ti, 0, n1)
print(ans)

Submission status: Accepted

Solution code:
def main():
    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 t in T:
        if t in S:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def search_number(key,S):
    left = 0
    right = len(S)
    while left < right:
        mid = (left + right) // 2
        if S[mid] == key:
            return True
        if S[mid] > key:
            right = mid
        elif S[mid] < key:
            left = mid + 1
    return False

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):
    if search_number(T[i],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 i in range(q):
    left=0
    right=n-1
    center=int((left+right)/2)
    while left<=right:
        center=int((left+right)/2)
        if s[center]==t[i]:
            cnt+=1
            break
        elif s[center]<t[i]:
            left=center+1
        else:
            right=center-1

print(cnt)

Submission status: Accepted

Solution code:
def search_binary(target_list, target_length, key_value):
    exit_flag = False
    left = 0
    right = target_length
    while left < right:
        mid = int((left + right)/2)
        if target_list[mid] == key_value:
            exit_flag = True 
            break
        elif target_list[mid] > key_value:
            right = mid
        else:
            left = mid + 1
    return exit_flag

target_length = int(input())
target_list = list(map(int,input().split()))
key_length = int(input())
key_list = list(map(int,input().split()))

exit_count = 0
for key_value in key_list:
    exit_count += 1 if search_binary(target_list, target_length, key_value) else 0
print(exit_count)

Submission status: Accepted

Solution code:
def func(n, t, q, s):
    matchN = 0
    for x in s:
        left = 0
        right = n
        while left < right:
            mid = int((left + right) / 2)
            if x == t[mid]:
                matchN += 1
                break
            elif x < t[mid]:
                right = mid
            else:
                left = mid + 1
    return matchN

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

Submission status: Accepted

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

def binarySearch(A, key):
    left = 0
    right = n

    while left < right:
        mid = (left + right) // 2
        if A[mid] == key:
            return 1

        elif key < A[mid]:
            right = mid
        else:
            left = mid+1
    return 0

C = 0
for i in T:
    C += binarySearch(S, i)
print(C)

Submission status: Accepted

Solution code:
def binarySearch(A, n, key):
	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


if __name__ == "__main__":
	n = int(input())
	S = list(map(int, input().split()))
	q = int(input())
	sum = 0
	for key in list(map(int, input().split())):
		if binarySearch(S, n, key):
			sum += 1
	print(sum)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
S = list(map(int, input().split()))
q = int(input())
P = list(map(int, input().split()))
count = 0

for i in P:
    left = 0
    right = n

    while left <= right:
        mid = (left + right) // 2
        # print("-------------------------")
        # print("i:{}".format(i))
        #
        # print("left:{}".format(left))
        # print("right:{}".format(right))
        # print("mid:{}".format(mid))
        # print("S[mid]:{}".format(S[mid]))

        if i == S[mid]:
            count += 1
            # print("found")
            break

        elif i < S[mid]:
            right = mid - 1
        else:
            left = mid + 1

print(count)

Submission status: Accepted

Solution code:
import sys
from sys import stdin
input = stdin.readline

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

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

k = int(input())
keys = list(map(int, input().split()))

cnt = 0
for key in keys:
    if BinarySearch(NUM_LIST, key, 0, len(NUM_LIST)):
        
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# 5
# 1 2 3 4 5
# 3
# 3 4 1

import copy

Sn = int(input())
S = list(map(int, input().split()))

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

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


if __name__ == "__main__":
    count = 0 
    for t in T:
        if binary_search(S, Sn, t):
            count += 1

    print(count)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_B
# pythonでは便利な実装がすでにあるのでそれを使えるように
# 実装例はここにある https://docs.python.org/ja/3/library/bisect.html#searching-sorted-lists

from bisect import bisect_left
# 他にもbisect, bisect_leftがあったりするが、重複した値があったときに右側を返すか左側を返すかの違い
# bisectはrightと一緒


def find_exact_equal(a: list, x: int):
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return 1  # 見つかったら1を返す。
    return 0  # 見つからなかったら0


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

cnt = 0
for t in T:
    cnt += find_exact_equal(S, t)

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()))

def binarysearch(x, i):
    left = 0
    right = len(x)
    while left < right:
        mid = (left + right) // 2
        if x[mid] == i:
            return True
        elif x[mid] < i:
            left = mid + 1
        else:
            right = mid
    return False
    
cnt = 0
for i in t:
    if binarysearch(s, i):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import bisect 
input()
S=list(map(int,input().split()))
input()
T=list(map(int,input().split()))
ans=0
for t in T:
  if bisect.bisect_left(S,t)!=bisect.bisect_right(S,t):
    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()))
ans = 0
for i in T:
    l = 0
    r = n
    while l<r:
        mid = (l+r)//2
        if S[mid] == i:
            ans+=1
            break
        elif S[mid]>i:
            r=mid
        elif S[mid]<i:
            l=mid+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 y in T:
    left=0
    right=len(S)
    while left<right:
        mid=(left+right)//2
        if S[mid]==y:
            count+=1
            break
        elif y<S[mid]:
            right=mid
        elif y>S[mid]:
            left=mid+1


print(count)

Submission status: Accepted

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

from bisect import bisect_right
def index_right(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_right(a, x)
    i = i-1
    if i != len(a) and a[i] == x:
        return i
    raise ValueError
    
ans = 0
for t in T:
    try:
        index_right(S, t)
        ans += 1
    except:
        continue
print(ans)

Submission status: Accepted

Solution code:
def binarySearch(S, x, l, r):
    if r-l<=1:
        if S[l]==x:
            return True
        else:
            return False
    else:
        m=(l+r)//2
        if x<S[m]:
            return binarySearch(S, x, l, m)
        elif S[m]<x:
            return binarySearch(S, x, m+1, r)
        else:
            return True

n=int(input())
S=list(map(int,input().split()))
q=int(input())
T=list(map(int,input().split()))
ans=0
for x in T:
    if binarySearch(S, x, 0, n):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def bs(array, n, v):
    l = 0
    r = n - 1
    while l <= r:
        p = (l + r) // 2
        if array[p] == v:
            return True
        elif v < array[p]:
            r = p - 1
        else:
            l = p + 1
    return False


def main():
    n = int(input())
    a = [int(i) for i in input().split()]

    input()
    b = [int(i) for i in input().split()]

    cnt = 0
    for i in b:
        if bs(a, n, i):
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
s=int(input())
S=list(map(int,input().split()))
t=int(input())
T=list(map(int,input().split()))
S=list(set(S))
ans=0
S.sort()
def bs(n,key,S):
  left=0
  right=n
  while left<right:
    mid=int((left+right)/2)
    if S[mid]==key:
      return 1
    elif key<S[mid]:
      right=mid
    else:
      left=mid+1
  return 0

for i in range(len(T)):
  if bs(len(S),T[i],S):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def binarySearch(A, key):
    left = 0
    right = len(A)
    while left < right:
        mid = (left + right) // 2
        if A[mid] == key:
            return mid
        elif A[mid] > key:
            right = mid
        else:
            left = mid + 1
    return "NOT_FOUND"

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

C = 0
for i in T:
    if binarySearch(S, i) != "NOT_FOUND":
        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 isOK(index,key):
    if S[index]>=key:
        return True
    else:
        return False


def binary_search(key):
    left=-1
    right=n

    while(right-left>1):
        mid = int(left+(right-left)/2)
        if isOK(mid,key):
            right = mid
        else:
            left = mid
    
    return right

ans=0
for x in T:
    index=binary_search(x)
    if x==S[index]:
        ans+=1
    

print(ans)

Submission status: Accepted

Solution code:
###
num = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]


def binsearch(list,q):
    min = 0
    max = len(list) -1
    mid = (min + max)//2
    while min <= max:
        #print(f"D:{min:>6} {mid:>6} {max:>6}: {list[mid]:>6}")
        if q < list[min]  or list[max] < q:
            return False
        if list[mid] == q:
            return True
        elif list[mid] > q:
            max = mid - 1
            mid = (min + max) // 2
        else:
            min = mid + 1
            mid = (min + max) // 2
    return False

count = 0
for k in t:
    if binsearch(s, k):
        count += 1
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left


def search(s, x):
    i = bisect_left(s, x)
    if i != len(s) and s[i] == x:
        return 1
    else:
        return -1


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

q = int(input())
t = list(map(int, input().split()))
cnt = 0
for num in t:
    if search(s, num) == 1:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys

def binarySearch(A,key):

	left = 0
	right = len(A)

	while left < right:

		mid = (left + right) // 2

		if A[mid] == key:
			return mid
		elif key < A[mid]:
			right = mid
		else:# A[mid] < key
			left = mid + 1

	return -1

def test():

	n = int(sys.stdin.readline())
	S = list(map(int,sys.stdin.readline().split()))
	q = int(sys.stdin.readline())
	T = list(map(int,sys.stdin.readline().split()))

	count = 0

	for i in range(q):
		find = binarySearch(S,T[i])
		if find != -1:
			count += 1

	print(f"{count}")

if __name__ == "__main__":
	test()

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 i in T:
    left = 0
    right = n - 1
    while left < right:
        mid = (left + right) // 2
        if i == S[mid]:
            cnt += 1
            break
        elif i < S[mid]:
            right = mid
        else:
            left = mid + 1
            if left == right:
                if i == S[left]:
                    cnt += 1
                    break

print(cnt)

Submission status: Accepted

Solution code:
import bisect

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

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

n_and_q = 0

for i in q:
    j = bisect.bisect_left(n, i)
    if i == n[j]:
        n_and_q += 1
        
print(n_and_q)

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(" ")]
searched = []

cnt = 0
for i in range(q):
    target = t[i]
    
    upper = n
    lower = 0
    while upper > lower:
        j = int((upper+lower)/2)
        
        if s[j] == target:
            cnt += 1
            break
        elif s[j] > target:
            upper = j
        elif s[j] < target:
            lower = j+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()))
count=0
for i in t:
	left,right=0,n
	while left<right:
		mid=(left+right)//2
		if s[mid] ==i:
			count+=1
			break
		elif s[mid]<i:
			left =mid+1
		else:
			right=mid
print(count)

Submission status: Accepted

Solution code:
def b_search(s_list,s, e, x):
    while (e-s) > 1:
        mid = (s + e) // 2
        w = s_list[mid]
        if w == x:
            return True
        elif w < x:
            s = mid+1
        elif w > x:
            e = mid

    if s_list[s] == x:
        return True
    else:
        return False

n_num = int(input())
n_list = [int(s) for s in input().split()]
q_num = int(input())
q_list = [int(s) for s in input().split()]

cnt = 0
for q in q_list:
    if b_search(n_list, 0, len(n_list)-1, q):
        cnt += 1

print(cnt)

Submission status: Accepted

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

def bs(alist, num):
  left = 0
  right = len(alist)
  while left < right:
    mid = (left + right) // 2
    if num == alist[mid]:
      return 1
    else:
      if alist[mid] < num:
        left = mid + 1
      else:
        right = mid

  return 0

ans = 0

for num in t:
  ans += bs(s, num)

print(ans)

Submission status: Accepted

Solution code:
import math

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

def main():
    n = int(input())
    S = [int(s) for s in input().split(" ")]
    _ = int(input())
    T = [int(s) for s in input().split(" ")]

    sum = 0

    for t in T:
        if binarySearch(S, n, t):
            sum += 1
    
    print(sum)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
S = [int(x) for x in input().split()]
q = int(input())
T = [int(x) for x in input().split()]

def BinarySearch(S,T):
    count = 0
    for i in range(q):
        left = 0
        right = n
        #right = n-1だとヒットするのがS[n-1]のみのときに見つからない
        #left < rightとmidは切り捨てより常にmid < right
        while left < right:
            mid = int((left + right) / 2)
            if T[i] == S[mid]:
                count += 1
                break
            elif T[i] < S[mid]:
                right = mid
            else:
                left = mid + 1
    return count

print(BinarySearch(S,T))

Submission status: Accepted

Solution code:
n = int(input())
S,T = set(),set()
a = [int(i) for i in input().split()]
for i in range(n):
    S.add(a[i])
n = int(input())
a = [int(i) for i in input().split()]
for i in range(n):
    T.add(a[i])
print(len(S&T))

"""
5
1 2 3 4 5
3
3 4 1
"""

Submission status: Accepted

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

center = int(n / 2)
result = 0

for ti in t:
  if s[center] < ti:
    left = int(n / 2)
    right = n - 1
  elif ti < s[center]:
    left = 0
    right = int(n / 2)
  else:
    result += 1
    continue

  while True:
    tmp = int(left + int((right - left) / 2))
    if 'current' in locals() and current == tmp:
      if right == (n - 1):
        current += 1
      else:
        current -= 1
    else:
      current = tmp

    if s[current] < ti:
      if current < left:
        break
      left = current
    elif ti < s[current]:
      if right < current:
        break
      right = current
    elif ti == s[current]:
      result += 1
      break

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()))

def binary_search(lst, n, val):
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if lst[mid] == val:
            return True
        elif lst[mid] < val:
            left = mid + 1
        elif lst[mid] > val:
            right = mid
    return False

ans = 0
for val in t:
    if binary_search(s, n, val):
        ans += 1

print(ans)

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(" ")]
 
print(len(set(S) & set(T)))

Submission status: Accepted

Solution code:
n = input()
s = set(input().split())
q = input()
t = set(input().split())
print(len(s & t))

Submission status: Accepted

Solution code:
n = input()
S = set(input().split())
q = input()
T = set(input().split())
print(len(S&T))

Submission status: Accepted

Solution code:
N = int(input())
SET = set()
table = list(map(int,input().split()))
 
for i in range(len(table)):
    SET.add(table[i])
 
ans = 0
 
num_query = int(input())
num_array = list(map(int,input().split()))
 
for i in range(len(num_array)):
    if num_array[i] in SET:
        ans += 1
 
print("%d"%ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    S = input().split()
    q = int(input())
    T = input().split() 
    a = set()
    count = 0
    for i in range(q):
        ch = 0
        j1 = 0
        j3 = len(S)-1
        j2 = int((j1+j3)/2)
        while j1<=j3:
            ch = j2
            if T[i] == S[j2]: 
                if T[i] in a: break
                else :
                    a.add(T[i])
                    count += 1
                    break
            elif int(T[i]) < int(S[j2]): 
                j3 = j2-1
                j2 = int((j1+j3)/2)
            elif int(T[i]) > int(S[j2]): 
                j1 = j2+1
                j2 = int((j1+j3)/2)
    
    print(str(count))

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    ns = list(map(int, input().split(' ')))
    _ = int(input())
    qs = list(map(int, input().split(' ')))
    count = 0
    start = 0
    end = n
    target = int((start + end) / 2)
    for q in qs:
        while end > start:
            if ns[target] > q:
                end = target
            elif ns[target] < q:
                start = target + 1
            else:
                count += 1
                break
            target = int((start + end) / 2)
        start = 0
        end = n
        target = int((start + end) / 2)
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections


if __name__ == "__main__":
    S_num = int(input())
    S = collections.Counter(set(map(lambda x: int(x), input().split())))
    T_num = int(input())
    T = list(map(lambda x: int(x), input().split()))

    print(f"{sum(map(lambda x: S[x], T))}")

Submission status: Accepted

Solution code:
if __name__ == '__main__':
	n = int(input())
	S = set([int(i) for i in input().split()])
	q = int(input())
	T = set([int(i) for i in input().split()])
	print(len(S&T))

Submission status: Accepted

Solution code:

def binary_search(arr, val):
    left = 0
    right = len(arr)

    while left < right:
        mid = (left + right)//2
        if arr[mid] == val:
            return mid
        elif arr[mid] < val:
            left = mid + 1
        else:
            right = mid
    return -1

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

    cnt = 0
    for i in T:
        if binary_search(S, i) != -1:
            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()))


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

ans = []
for i in t:
    v = binSearch(s, i)
    if v != False:
        ans.append(v)

print(len(set(ans)))