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: Time Limit Exceeded

Solution code:
def binary_search(ls, val):
    ls_norm = len(ls)

    if ls_norm == 0:
        return -1

    mid = int(ls_norm / 2)

    if ls[mid] == val:
        return mid
    elif ls[mid] > val:
        return binary_search(ls[0: mid], val)
    else:
        return binary_search(ls[mid + 1:], val)

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

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

result = 0
for t in T:
    if binary_search(S, t) != -1:
        result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int, input().split())) # in演算子を使うためにはsはlistである必要がある。
q = int(input())
t = map(int, input().split())

cnt = 0

for i in t:
    if i in s:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
cnt=0
n=int(input())
S=[0 for i in range(n)]
S=input().split()
q=int(input())
T=[0 for i in range(q)]
T=input().split()
for i in range(q):
    p=0
    for j in range(n):
        if T[i]==S[j]:
            if p==0:
                cnt+=1
                p+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input().split()
q = int(input())
t = input().split()
c = 0

for i in t:
    l = 0
    r = n
    cen = int((l+r) / 2)
    while r > l :
        if i > s[cen]:
            l = cen
            cen = int((l+r) / 2)
        elif i < s[cen]:
            r = cen
            cen = int((l+r) / 2)
        elif i == s[cen]:
            c += 1
            break
print(c)

Submission status: Time Limit Exceeded

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

for i in t:
    l = 0
    r = n-1
    cen = int((l+r) / 2)
    while r >= l :
#        print("0:",i,l,r,cen,s[cen])
        if i > s[cen]:
            l = cen
            cen = int((l+r) / 2)
#            print("1:",l,r,cen,s[cen])
        elif i < s[cen]:
            r = cen
            cen = int((l+r) / 2)
#            print("2:",l,r,cen,s[cen])
        if i == s[cen]:
            c += 1
#            print("!")
            break
        if l+1 == r-1:
#            print("!!")
            break
print(c)

Submission status: Time Limit Exceeded

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

for i in t:
    l = 0
    r = n-1
    cen = int((l+r) / 2)
    while r >= l :
#        print("0:",i,l,r,cen,s[cen])
        if i > s[cen]:
            l = cen
            cen = int((l+r) / 2)
#            print("1:",l,r,cen,s[cen])
        elif i < s[cen]:
            r = cen
            cen = int((l+r) / 2)
#            print("2:",l,r,cen,s[cen])
        if i == s[cen] or i == s[l] or i == s[r]:
            c += 1
#            print("!")
            break
        if l+1 == cen and r-1 == cen:
#            print("!!",i)
            break
print(c)

Submission status: Time Limit Exceeded

Solution code:
sn = int(input())
S = [0 for i in range(sn)]
S = input().split()
for i in range(sn):
	S[i] = int(S[i])

tn = int(input())
T = [0 for i in range(tn)]
T = input().split()
for i in range(tn):
	T[i] = int(T[i])

A=[]
cnt=0

for i in range(tn):

	key=T[i]
	left=0
	right=sn

	while left<right:

		mid=(int)((left+right)/2)

		if S[mid]==key:
			if T[i] not in A:
				cnt+=1
			A.append(key)
			break

		if S[mid]>key:
			right=mid
			
		if S[mid]<key:
			left=mid+1


print(cnt)

Submission status: Time Limit Exceeded

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

n = int(input())
T = list(map(int, input().split()))
cnt = 0

for i in T:
    left = 0
    right = len(S)-1
    center = int( (left+right) / 2 )

    while center >= left and center <= right:
        if S[center] == i:
            cnt += 1
            break
        elif S[center] > i:
            right = center-1
            center = int( (left+right) / 2 )
        elif S[center] < i:
            left = center-1
            center = int( (left+right) / 2 )

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=input().split()

m=int(input())
b=input().split()

a=[int(i) for i in a]
b=[int(i) for i in b]

a.sort()
b.sort()
cnt=0

for j in range(m):
  if b[j] in a:
    cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
Q=input().split()
q=int(input())
S=input().split()

Q=list(map(int,Q))
S=list(map(int,S))

cnt=0

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:

n=int(input())
S=[]
S=input().split()
q=int(input())
T=[]
T=input().split()
point=0
for i in range(q):	
	for j in range(n):
		if T[i]==S[j]:
			point+=1
			break
			
print(point)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
S=[]
S=input().split()
q=int(input())
T=[]
T=input().split()
point=0
for i in range(q):	
	for j in range(n):
		if T[i]==S[j]:
			point+=1
			break		
print(point)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

l=0
r=len(A)
c=(r+l)/2

n=0


for i in B:
    if i in A:
        n+=1
    elif i>c:
        l=c+1
        c=(r+l)/2
    elif i<c:
        r=c
        c=(r+l)/2

print(n)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

l=0
r=len(A)
c=(r+l)/2

n=0


for i in B:
    if i in A:
        n+=1
    elif i>c:
        l=c+1
        c=(r+l)/2
    else:
        r=c
        c=(r+l)/2

print(n)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

l=0
r=len(A)
c=(r+l)/2

n=0


for i in B:
    cnt=0
    if i in A and cnt==0:
        n+=1
        cnt+=1
    elif i>c:
        l=c+1
        c=(r+l)/2
    else:
        r=c
        c=(r+l)/2

print(n)

Submission status: Time Limit Exceeded

Solution code:
def binary_search(v,r):
    if len(r)==0:
        return False
    if len(r)==1:
        if v==r[0]:
            return True
        else:
            return False
 
    half=int(len(r)/2)
    if(r[half]==v):
        return True
 
    if r[half]>v:
        return binary_search(v,r[:half])
    else:
        return binary_search(v,r[half+1:])
 
n=int(input())
s=[]
l=input()
s=l.split(" ")
for i in range(n):
   s[i]=int(s[i])
 
q=int(input())
l=input()
t=l.split(" ")
for i in range(q):
    t[i]=int(t[i])
 
cnt=0
for i in range(q):
    if binary_search(t[i],s):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def binary_search(v,r):
    s=0
    e=len(r)
    while True:
        half=int((s+e)/2)
        if r[half]==v:
            return True
        if(half<=1):
            return False
        elif r[half]<v:
            s=half
        else:
            e=half
        
 
n=int(input())
s=[]
l=input()
s=l.split(" ")
for i in range(n):
   s[i]=int(s[i])
 
q=int(input())
l=input()
t=l.split(" ")
for i in range(q):
    t[i]=int(t[i])
 
cnt=0
for i in range(q):
    if binary_search(t[i],s):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def binary_search(v,r):
    s=0
    e=len(r)
    while True:
        half=int((s+e)/2)
        if r[half]==v:
            return True
        if(half<1):
            return False
        elif r[half]<v:
            s=half
        else:
            e=half
        
 
n=int(input())
s=[]
l=input()
s=l.split(" ")
for i in range(n):
   s[i]=int(s[i])
 
q=int(input())
l=input()
t=l.split(" ")
for i in range(q):
    t[i]=int(t[i])
 
cnt=0
for i in range(q):
    if binary_search(t[i],s):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def binary_search(v,r):
    s=0
    e=len(r)-1
    while True:
        half=int((s+e)/2)
        if r[half]==v:
            return True
        if(half<=1):
            return False
        elif r[half]<v:
            s=half
        else:
            e=half
        
 
n=int(input())
s=[]
l=input()
s=l.split(" ")
for i in range(n):
   s[i]=int(s[i])
 
q=int(input())
l=input()
t=l.split(" ")
for i in range(q):
    t[i]=int(t[i])
 
cnt=0
for i in range(q):
    if binary_search(t[i],s):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def binary_search(v,r):
    s=0
    e=len(r)-1
    while True:
        half=int((s+e)/2)
        #print(s," ",e," ",half)
        if r[half]==v:
            return True
        if(half<1):
            return False
        elif r[half]<v:
            s=half+1
        else:
            e=half-1
        
 
n=int(input())
s=[]
l=input()
s=l.split(" ")
for i in range(n):
   s[i]=int(s[i])
 
q=int(input())
l=input()
t=l.split(" ")
for i in range(q):
    t[i]=int(t[i])
 
cnt=0
for i in range(q):
    if binary_search(t[i],s):
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
for i in t:
	for j in s:
		if int(i)==int(j):
			c +=1
			break
print(c)

Submission status: Time Limit Exceeded

Solution code:
c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
s.sort()
for i in t:
	for j in s:
		if int(i)==int(j):
			c +=1
			break
print(c)

Submission status: Time Limit Exceeded

Solution code:
c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
s.sort()
l=list(set(s))
for i in t:
	for j in l:
		if int(i)==int(j):
			c +=1
			break
print(c)

Submission status: Time Limit Exceeded

Solution code:
c=0
n=int(input())
s=input().split()
q=int(input())
t=input().split()
l=list(set(s))
l.sort()
for i in t:
	for j in l:
		if int(i)==int(j):
			c +=1
			break
print(c)

Submission status: Time Limit Exceeded

Solution code:
S=[]
T=[]
n=int(input())
s=input().split()
for i in range(n):
	S.append(s[i])
q=int(input())
t=input().split()
for j in range(q):
	T.append(t[j])
cnt=0
for i in range(q):
	for j in range(n):
		if T[i]==S[j]:
			cnt+=1
			break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S=[]
T=[]
n=int(input())
s=input().split()
for i in range(n):
	S.append(s[i])
q=int(input())
t=input().split()
for j in range(q):
	T.append(t[j])
cnt=0
for i in range(q): #T
	for j in range(n): #S
		if T[i]==S[j]:
			cnt+=1
			break
			if S[j+1]==S[j]:
				break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S=[]
T=[]
n=int(input())
s=input().split()
for i in range(n):
	S.append(s[i])
q=int(input())
t=input().split()
for j in range(q):
	T.append(t[j])
cnt=0
for i in range(q): #T
	for j in range(n): #S
		if T[i]==S[j]:
			cnt+=1
			break
			if S[j+1]==S[j]:
				pass
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
S=[]
T=[]
n=int(input())
s=input().split()
for i in range(n):
	S.append(s[i])
q=int(input())
t=input().split()
for j in range(q):
	T.append(t[j])
cnt=0
for i in range(q): #T
	for j in range(n): #S
		if T[i]==S[j]:
			cnt+=1
			break
			if S[j+1]==S[j]:
				j+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lista=[0 for i in range(n)]
lista=input().split()
n2=int(input())
listb=[0 for i in range(n2)]
listb=input().split()
cnt=0
for i in range(n2):
    x=0
    for j in range(n):
        if listb[i]==lista[j] and x==0:
            x=1
            cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
lista=[0 for i in range(n)]
lista=input().split()
n2=int(input())
listb=[0 for i in range(n2)]
listb=input().split()
cnt=0

for i in range(n2):
    x=0

    
    if int(lista[int(n/2)])>int(listb[i]):
        listc=[lista[k] for k in range(int(n/2))]
    
        for j in range(len(listc)):
            if listb[i]==listc[j] and x==0:
                
                x=1
                cnt+=1
    else: 
        listc=[lista[k] for k in range(int(n/2),n)]
      
        for j in range(len(listc)):
          
            if listb[i]==listc[j] and x==0:
               
                x=1
                cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

cnt = 0
for t in T:

    S = deepcopy(S_origin)
    while S:
        ind = len(S) // 2

        if t == S[ind]:
            cnt += 1
            break
        elif t < S[ind]:
            S = S[:ind]
        else:
            S = S[ind + 1:]

print(cnt)

Submission status: Time Limit Exceeded

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

# from copy import deepcopy

# for t in T:
#     S_ = deepcopy(S)

#     while S_:
#         ind = len(S_) // 2

#         if t == S_[ind]:
#             cnt += 1
#             break
#         elif t < S_[ind]:
#             S_ = S_[:ind]
#         else:
#             S_ = S_[ind + 1:]


def binary_search(ary, target):

    if ary:
        ind = len(ary) // 2
        if target == ary[ind]:
            return True
        elif target < ary[ind]:
            return binary_search(ary[:ind], target)
        else:
            return binary_search(ary[ind + 1:], target)

    else:
        return False


for target in T:
    if binary_search(S, target):
        cnt += 1

if __name__ == '__main__':
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline().strip())
S = [int(_) for _ in sys.stdin.readline().strip().split()]
q = int(sys.stdin.readline().strip())
T = [int(_) for _ in sys.stdin.readline().strip().split()]
cnt = 0


def binary_search(ary, target):

    if ary:
        ind = len(ary) // 2
        if target == ary[ind]:
            return True
        elif target < ary[ind]:
            return binary_search(ary[:ind], target)
        else:
            return binary_search(ary[ind + 1:], target)

    else:
        return False


for target in T:
    if binary_search(S, target):
        cnt += 1

if __name__ == '__main__':
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

n = int(sys.stdin.readline().strip())
S = [int(_) for _ in sys.stdin.readline().strip().split()]
q = int(sys.stdin.readline().strip())
T = [int(_) for _ in sys.stdin.readline().strip().split()]
cnt = 0


def binary_search(ary, target):

    if ary:
        ind = len(ary) // 2
        if target == ary[ind]:
            return True
        elif target < ary[ind]:
            return binary_search(ary[:ind], target)
        else:
            return binary_search(ary[ind + 1:], target)

    else:
        return False


for target in T:
    if binary_search(S, target):
        cnt += 1

if __name__ == '__main__':
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# ALDS1_4_B.
# バイナリサーチ。

def intinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def main():
    n = int(input())
    S = intinput()
    q = int(input())
    T = intinput()
    count = 0
    for k in T:
        if k in S: count += 1
    print(count)

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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 range(q):
    for j in range(n):
        if t[i] == s[j]:
            ans += 1
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
S=[int(i) for i in input().split()]
q=int(input())
T=[int(i) for i in input().split()]
s=0
for i in range(q):
    if T[i] in S:
        s+=1
print(s)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))
count = 0
for a in t:
    left = 0
    right = n - 1
    while left <= right:
        mid = (right + left) // 2
        if a == s[mid]:
            count += 1
            break
        elif a < s[mid]:
            right = mid
        else :
            left = mid + 1

print(count)

Submission status: Time Limit Exceeded

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

n = int(input())
s = list(input().split())
n = int(input())
t = list(input().split())
cnt = 0
for i in range(n):
    if t[i] in s:
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
L = input().split()
L = [int(s) for s in L]
n = int(input())
l = input().split()
l = [int(s) for s in l]
ans = 0
for i in range(n):
    j = 0
    k = N-1
    while(j != k):
    #for m in range(5):
        a =  int((j + k)/2)
        if l[i] > L[a]:
            j = a
        elif l[i] < L[a]:
            k = a
        else:
            ans += 1
            break
        #print(j,k,a,ans)
        #print(l[i],L[a])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
n=input()
S=map(int, raw_input().split())
q=input()
T=map(int, raw_input().split())
#?????????????????????????????????
s=sorted(set(S), key=S.index)
t=sorted(set(T), key=T.index)
ST=s+t
t=set()
m=[x for x in ST if x in t or t.add(x)]
#print ' '.join(map(str, m))
print len(m)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
#start = time.clock()
#i = 0
n=input()
S=map(int, raw_input().split())
q=input()
T=map(int, raw_input().split())
s=sorted(set(S), key=S.index)
st=set(s)-set(T)
ST=list(st)
print len(s)-len(ST)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-
#from __future__ import print_function
import time
import sys
import io
import re
import math
start = time.clock()
i = 0
n=input()
S=map(int, raw_input().split())
q=input()
T=map(int, raw_input().split())
s=sorted(set(S), key=S.index)
print len(set(s)&set(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 binary_search(target_num, head, tail):
    idx = int((head+tail)/2)
    if target_num == S[idx]:
        return True
    elif target_num < S[idx]:
        if head == idx:
            return False
        return binary_search(target_num, head, idx-1)
    else:
        if tail == idx:
            return False
        return binary_search(target_num, idx+1, tail)


match_count = 0
for target_num in T:
    if binary_search(target_num, 0, len(S)-1):
        match_count += 1

print(str(match_count))

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(target_num, head, tail):
    while head <= tail:
        idx = int((head+tail)/2)
        if target_num == S[idx]:
            return True
        elif target_num < S[idx]:
            tail = idx - 1
        else:
            head = idx + 1
    return False


match_count = 0
for target_num in T:
    if binary_search(target_num, 0, len(S)-1):
        match_count += 1

print(str(match_count))

Submission status: Accepted

Solution code:
N = int(input())
S = set(input().split())
Q = int(input())
T = set(input().split())
print(len(S & T))

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):
    l = 0
    r = n
    t = T[i]
    while r-l > 1:
        m = (r + l)//2
        if (S[m] > t):
            r = m
        else:
            l = m
    if (S[l] == T[i]):
        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 binary_search(series, key, i_left, i_right):
    if i_right == i_left:
        return int(series[i_right] == key)
    i_center = int((i_left + i_right)/2)
    if series[i_center] == key:
        return 1
    elif series[i_center] > key:
        return binary_search(series, key, i_left, i_center)
    else:
        return binary_search(series, key, i_center + 1, i_right)

cnt = 0
for t in T:
    cnt += binary_search(S, t, 0, n-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 binary_search(S, key):
    left = 0
    right = n
    while left < right:
        mid = (left + right) // 2
        if S[mid] == key:
            return True
        elif S[mid] > key:
            right = mid
        else:
            left = mid + 1
    return False

print(sum(binary_search(S, key) for key in T))

Submission status: Accepted

Solution code:
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))
import bisect
 
N=iipt()
c=miipt()
M=iipt()
qu=miipt()
ans=0
for q in qu:
    a=0
    b=N-1
    while b-a>1:
        x=(a+b)//2
        if c[a]==q or c[b]==q:
            ans+=1
            break
        if c[x]<q:
            a=x
        else:
            b=x
    else:
        if c[a]==q or c[b]==q:
            ans+=1

    """        
    if a==-1 or b==N:
        print(q,a,b)
        ans-=1"""

print(ans)

Submission status: Accepted

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

ans=0
for t in T:
    if S[-1]<t or S[0]>t: continue
    U=n
    L=0
    while True:
        x=(U+L)//2
        if S[x]==t:
            ans+=1
            break
        elif U-L==1:
            break
        elif S[x]>t:
            U=x
        else:
            L=x
print(ans)

Submission status: Accepted

Solution code:
Ns=int(input())
S=list(map(int,input().split()))
Nt=int(input())
T=list(map(int,input().split()))

answer=0

for i in range(0,len(T)):
    a=0
    b=len(S)-1
    
    while b-a>=2:
        x=(a+b)//2
        
        if T[i]>=S[x]:
            a=x
        else:
            b=x
            
    if T[i]==S[a] or T[i]==S[b]:
        answer+=1
    
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
sinput = input().split()
s=[]
for i in range(n):
    s.append(int(sinput[i]))

q = int(input())
tinput = input().split()
t=[]
for i in range(q):
    t.append(int(tinput[i]))
answer = 0

import math
for tn in t:
    smin = 0
    smax = n - 1
    c = math.floor((n - 1) / 2)
    while(smax - smin > 1):
        if(tn == s[c]):
            answer = answer + 1
            break
        elif(tn > s[c]):
            if(tn == s[smax]):
                answer = answer + 1
                break
            smin = c
            c = math.floor((smin + smax) / 2) 
        elif(tn < s[c]):
            if(tn == s[smin]):
                answer = answer + 1
                break
            smax = c
            c = math.floor((smin + smax) / 2)

print(answer)

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


def b_search(x, y):
    a = 0
    b = len(x)
    if y > x[b-1] or y < x[a]:
        return 0
    while b - a > 1:
        c = (a + b) // 2
        if x[c] == y:
            return 1
        elif y < x[c]:
            b = c
        else:
            a = c
    return 0


for i in range(len(t)):
    count += b_search(s, t[i])

print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
#二分探索の実装

N=int(input())
S=[int(i) for i in input().split()]
Q=int(input())
T=[int(i) for i in input().split()] 
C=0
a=0;b=0
for i in T:
    b=len(S)-1
    a=0
    while(a+1<b):
        c=((a+b)//2)
        if(S[c]>=i):
            b=c
        elif(S[c]<i):
            a=c
    if(S[a]==i or S[b]==i):
        C+=1
print(C);

Submission status: Accepted

Solution code:
Ns=int(input())
S=list(map(int,input().split()))
Nt=int(input())
T=list(map(int,input().split()))

answer=0

for i in range(0,len(T)):
    a=0
    b=len(S)-1
    
    while b-a>1:
        x=(a+b)//2
        
        if T[i]>=S[x]:
            a=x
        else:
            b=x
            
    if T[i]==S[a] or T[i]==S[b]:
        answer+=1
        
print(answer)

Submission status: Accepted

Solution code:
def binary_search(array, tgt_no): #  arrayは昇順にソートされているものとする

    def compare_midpoint(tgt, array, start, end):
        midpoint = (end + start)//2
        if tgt == array[midpoint]:
            return True, None, None
        elif tgt < array[midpoint]:
            return False, start, midpoint
        elif tgt > array[midpoint]:
            return False, midpoint, end

    start = 0
    end = len(array)
    while True:
        ret, start, end = compare_midpoint(tgt_no, array, start, end)
        if ret:
            return True
        if end - start <= 1:
            return tgt_no == array[start]


def main():
    _ = input()
    array_A = list(map(int, input().split()))
    _ = input()
    array_B = list(map(int, input().split()))

    cnt = 0
    for integer_B in array_B:
        if binary_search(array_A, integer_B):
            #print(integer_B)
            cnt += 1

    print(cnt)
    return


main()

Submission status: Accepted

Solution code:
def binary_search(array, tgt_no): #  arrayは昇順にソートされているものとする

    def compare_midpoint(tgt, array, start, end):
        midpoint = (end + start)//2
        if tgt == array[midpoint]:
            return True, None, None
        elif tgt < array[midpoint]:
            return False, start, midpoint
        elif tgt > array[midpoint]:
            return False, midpoint + 1, end

    start = 0
    end = len(array)
    while True:
        ret, start, end = compare_midpoint(tgt_no, array, start, end)
        if ret:
            return True
        if end <= start:
            return False


def main():
    _ = input()
    array_A = list(map(int, input().split()))
    _ = input()
    array_B = list(map(int, input().split()))

    cnt = 0
    for integer_B in array_B:
        if binary_search(array_A, integer_B):
            #print(integer_B)
            cnt += 1

    print(cnt)
    return


main()

Submission status: Accepted

Solution code:
def binary_search(num_list,target):
    first = 0
    last  = len(num_list)-1
    mid   = len(num_list)//2

    while first <= last:
        if   num_list[mid] == target:
            return 1
        elif num_list[mid] >  target:
            last = mid-1 
        elif num_list[mid] <  target:
            first = mid+1
        mid = (first+last)//2
    return 0

n = input()
num_list    = list(map(int,input().split()))
q = input()
target_list = list(map(int,input().split()))
ans = 0

for target in target_list:
    ans += binary_search(num_list,target)
print(ans)

Submission status: Accepted

Solution code:
import copy

NOT_FOUND = False

# 二分探索
def binarySearch(n, S, t):
     
    left = 0
    right = n
    key = t
    while left < right:
        mid = (left + right) // 2
        if S[mid] == key:
            return True
        elif key < S[mid]:
            right = mid
        else:        
            left = mid + 1
    return NOT_FOUND
 
if __name__ == '__main__':
     
    # 入力
    n = int(input()) # 数列Sに含まれる整数の個数
    S = list(map(int,input().split())) # 整数を含む数列
    q = int(input()) # 数列Tに含まれる異なる整数の個数
    T = list(map(int,input().split())) # 異なる整数を含む数列
     
    # 初期化
    C = 0 # Tに含まれる整数の中でSに含まれるものの個数
     
    # 数列T内の整数を1つずつチェック
    for i in range(q):
        isExist = binarySearch(n, S, T[i])
         
        # 存在してたらカウント
        if isExist :
            C = C + 1
    # 出力
    print(C)

Submission status: Accepted

Solution code:
def main():
    input()
    s = [int(i) for i in input().split()]
    input()
    t = [int(i) for i in input().split()]
    number = 0
    for ti in t:
        start, stop = 0, len(s)-1
        while stop - start > 1:
            center = int((start + stop) / 2)
            if ti < s[center]:
                stop = center
            elif ti > s[center]:
                start = center
            else:
                number += 1
                break
        else:
            if ti == s[start] or ti == s[stop]:
                number += 1
    print(number)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def binary_search(arr,key):
	left = 0 
	right = len(arr)
	while left < right:
		mid = (left + right)//2
		if arr[mid] == key:
			return mid 
		elif arr[mid] < key:
			left = mid + 1
		else:
			right = mid
	return -1
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):
	if binary_search(S, T[i]) != -1:
		count += 1

print(str(count))

Submission status: Accepted

Solution code:
from typing import List
import math

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


def binary_search(A: List[int], key: int) -> int:
    left = 0
    right = len(A)
    while left < right:
        mid = math.floor((left + right) / 2)
        if A[mid] == key:
            return mid
        elif key < A[mid]:
            right = mid
        else:
            left = mid + 1
    return -1


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

Submission status: Accepted

Solution code:
#! python3
# binarySearch.py - 二分探査を行う

def binarySearch(num_list, value):
    lo = 0
    hi = len(num_list)
    while lo < hi:
        mid = int((lo + hi) / 2)
        if num_list[mid] == value:
            return True
        elif value < num_list[mid]:
            hi = mid
        elif value > num_list[mid]:
            lo = mid + 1
    return False

num_of_S = int(input())
S = [int(i) for i in input().split()]
num_of_T = int(input())
T = [int(i) for i in input().split()]

cnt = 0
for i in range(num_of_T):
    if binarySearch(S, T[i]):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
input()
n1 = set(input().split())
input()
n2 = set(input().split())

print(len(n1&n2))