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

count = 0

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

def find(key,l,r):
    m = int(l+(r-l)/2)
    #print(str(key) + " " + str(l) + " " + str(m) + " " + str(r))
    if key == S[m]:
        return True
    elif r-l <= 1:
        return False
    elif key < S[m]:
        return find(key,l,m)
    elif key > S[m]:
        return find(key,m+1,r)

cnt = 0
for x in T:
    if find(x,0,n) is True:
        cnt += 1
    
print(cnt)

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

ans = 0
for i in range(q):
    L = 0
    R = n
    while L + 1 < R:
        M = (L + R) // 2
        if S[M] <= T[i]:
            L = M
        else:
            R = M

    find = S[L] == T[i]
    ans = ans + find
print(ans)

Submission status: Accepted

Solution code:
def find_sorted(elt, sarray):
    """Finds an element in a sorted array.

    Args:
        elt (int)     -- Element to search
        array (array) -- Sorted array (element in increasing order)
    Returns:
        Index of "elt" in "array", or "None" if "elt" is not in "array"
    """
    # TODO: remove the line below, and...
    # return find(elt, sarray)
    # TODO: ...implement using the knowledge that
    # TODO: the input array is already sorted.
    left = 0
    right = len(sarray)
    while left < right:
        mid = (left + right) // 2
        if sarray[mid] == elt:
            return mid
        elif sarray[mid] < elt:
            left = mid + 1
        else:
            right = mid
    else:
        return None

n  = int(input())
S = list(map(int,input().split()))
q = int(input())
T = list(map(int,input().split()))
count = 0
for i in range(len(T)):
    if find_sorted(T[i],S) != None:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import sys

sys.stdin.readline()
s = set(map(int, sys.stdin.readline().split()))
sys.stdin.readline()

print(sum(
    t in s
    for t in map(int, sys.stdin.readline().split())
))

Submission status: Accepted

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

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

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

	cnt = 0
	for i in range(q):
		if (binarySearch(L, n, Key[i])):
			cnt += 1

	print(cnt)

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp
#  Binary Search : python3
#  2018.12.08 yonezawa


#from collections import deque
import sys
input = sys.stdin.readline
#import cProfile

def main():
    n1 = int(input())
    s1 = set(map(int,input().split()))
    n2 = int(input())
    s2 = set(map(int,input().split()))
    print (len(s1 & s2))

if __name__ == '__main__':
   main()
#    pr = cProfile.Profile()
#    pr.runcall(main)
#    pr.print_stats()

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

Submission status: Accepted

Solution code:
#-*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B
"""
def input_array():
    n = int(input())
    S = list(map(int, input().split()))
    return S

def input_from_txt():
    import requests
    url = "https://judgedat.u-aizu.ac.jp/testcases/ALDS1_4_A/8/in"
    res = requests.get(url)
    input = res.text.split("\n")
    n = input[0]
    S = list(map(int, input[1].split()))
    q = input[2]
    T = list(map(int, input[3].split()))
    return (n, S, q, T)

# O(n^2)
def get_set(S, T):
    C = []
    for s in S:
        for t in T:
            if s == t: C.append(t)
    return C

# O(n^2) ??
def get_set2(S, T):
    return list(set(S).intersection(set(T)))

# O(log(n)) + O(n+q) = O(n)
def get_set3(S:list, T:list):
    D:dict = {}
    C = []
    for s in S:
        D[s] = 1
    for t in T:
        if t in D.keys() and D[t] == 1:
            D[t] = 2
            C.append(t)
    return C


if __name__ == '__main__':
    S = input_array()
    T = input_array()
    #(n, S, q, T) = input_from_txt()
    #print(n, S, q, T)
    ret = get_set3(S, T)
    print(len(set(ret)))

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split(" ")))
n = int(input())
T = list(map(int, input().split(" ")))
def divide(A,a):
    left = 0
    right = len(A)
    
    while left < right:
        mid = (left + right)//2
        if a < A[mid]:
            right = mid
        elif A[mid] < a:
            left = mid + 1
        else:
            return True
    return False
cnt = 0
for t in T:
    if t < S[0] or S[-1] < t:
        continue
    if divide(S,t):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8

def binary_search(key, A):
    left = 0
    right = len(A)
    while left < right:
        mid = int((left + right) / 2)
        if A[mid] == key:
            return mid
        elif key < A[mid]:
            right = mid
        elif key > A[mid]:
            left = mid + 1
    return 'Not Found'

if __name__ == "__main__":
    # n = 5
    # S = list(map(int, '1 2 3 4 5'.split()))
    # q = 3
    # T = list(map(int, '3 4 1'.split()))
    n = int(input())
    S = list(map(int, input().strip().split()))
    q = int(input())
    T = list(map(int, input().strip().split()))

    c = 0
    for k in T:
        if binary_search(k, S) != 'Not Found':
            c += 1
    print(c)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_B


def solve():
    _ = int(input())
    S = set(map(int, input().split()))
    _ = int(input())
    T = set(map(int, input().split()))

    print(len(S & T))


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

    cnt = 0
    for key in T:
        if binarySearch(S,key):
            cnt +=1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n1=int(input())
a=list(map(int,input().split()))
n2=int(input())
b=list(map(int,input().split()))
c=[]
d=0
for i in b:
		left=0
		right=n1
		while left<right:
			mid=int((left+right)/2)
			if i==int(a[mid]):
				d+=1
				break
			elif i<a[mid]:
				right=mid
			else:
				left=mid+1
print(d)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def binarySearch(alist, item):
    left=0
    right=len(alist)
    found = False
    while left < right and not found:
        mid=int((left+right)/2)
        if alist[mid] == item:
            found=True
        elif item<=alist[mid]:
            right=mid
        else:
            left=mid+1
    return found

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

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

s_unique = list(set(slist))
s_unique.sort()

cnt = 0
for t in tlist:
    low = 0
    high = len(s_unique)
    s = (low + high) // 2

    while low <= high:
        if t == s_unique[s]:
            break
        elif t > s_unique[s]:
            low = s + 1
        elif t < s_unique[s]:
            high = s - 1
        s = (low + high) // 2

    if t == s_unique[s]:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
s = [-1]
s.extend(list(map(int,input().split())))
q = int(input())
lfin=list(map(int,input().split()))
ans = 0

for item in lfin:
    ok = n
    ng = 0
    while(abs(ok-ng)>1):
        num = (ok+ng)//2
        if s[num] >= item:
            ok = num
        else:
            ng = num
    else:
        if s[ok] == item:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math

s_num=int(input())
s_list=list(map(int,input().split()))
q_num=int(input())
q_list=list(map(int,input().split()))


count = 0

for q in q_list:
    left = 0
    right = s_num
    while left < right:
        mid = math.floor((left + right) / 2)
        if s_list[mid] == q:
            count += 1
            break
        elif s_list[mid] < q:
            left = mid+1
        else:
            right = mid

print(count)

Submission status: Accepted

Solution code:
def binary_search(key,S,start,end):
    if(start > end):
        return 0
    tmp_med=(start + end)//2
    if(S[tmp_med] == key):
        return 1
    elif(S[tmp_med] <key):
        return binary_search(key,S,tmp_med + 1, end)
    else:
        return binary_search(key,S,start,tmp_med-1)





n=int(input())
S=input().split()

q=input()
T=input().split()

S.sort()

cnt=0
for x in T:
    cnt+=binary_search(x,S,0,n-1)

print(cnt)

Submission status: Accepted

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


def Binary_Search(A, key):
    A_left = 0
    A_right = n
    while A_left < A_right:
        mid = (A_right+A_left) // 2
        if A[mid] < key:
            A_left = mid+1
        elif key < A[mid]:
            A_right = mid
        else:
            return mid
    return "Not_Found"


sol_coun = 0
for i in t:
    if Binary_Search(s, i) != "Not_Found":
        sol_coun += 1
    else:
        continue
print(sol_coun)

Submission status: Accepted

Solution code:
import math

def binarySearch(key, nums, left=0, right=None):
    if right == None:
        right = len(nums)-1

    if right < left:
        return 0

    mid = math.floor((right - left)/2)+left

    if key == nums[mid]:
        return 1

    if key < nums[mid]:
        return binarySearch(key, nums, left ,mid-1)
    else:
        return binarySearch(key, nums, mid+1 ,right)

def main():
    input()
    ss = [int(x) for x in input().split()]

    input()
    ts = [int(x) for x in input().split()]

    nums = {}
    cnt = 0

    for t in ts:
        if t in nums:
            continue;

        nums[t] = binarySearch(t, ss)
        cnt += nums[t]

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.stdin.readline()
ss = list(map(int,sys.stdin.readline().split()))
sys.stdin.readline()
tt = list(map(int,sys.stdin.readline().split()))

cnt = 0
for t in tt:
    beg = 0
    end = len(ss)-1
    while beg<=end:
        ctr = (beg+end)//2
        if t==ss[ctr]:
            cnt += 1
            break
        elif t<ss[ctr]:
            end=ctr-1
        else: # t>s[ctr]                                                        
            beg=ctr+1
print(cnt)

Submission status: Accepted

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

n = int(input())
list_s = list((map(int, input().split())))
q = int(input())
list_t = list((map(int, input().split())))
ans = 0
for numbert in list_t:
    if binarySearch(list_s,numbert) != "NOT_FOUND":
        ans += 1
    
print(ans)

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:
#119
#ALDS1_4_A
n = input()
s = set(input().split())
m = input()
t = set(input().split())
print(len(s&t))

Submission status: Accepted

Solution code:
import sys

# Set max recursion limit
sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]


def is_exist(A, x):
    l = 0
    r = len(A) - 1

    while l <= r:
        m = (l + r) // 2
        if A[m] == x:
            return True
        
        if A[m] < x:
            l = m + 1
        else:
            r = m - 1

    return False
            


def main():
    n = int(input())
    S = li_input()
    q = int(input())
    T = li_input()

    ans = 0

    for t in T:
        if is_exist(S, t):
            ans += 1

    print(ans)


main()

Submission status: Accepted

Solution code:
a = input()
b = list(map(int, input().split()))
c = input()
d = list(map(int, input().split()))

def binary_search(A, f, t, val):
    n = (t + f) // 2
    # この終了条件ではt と f　間の関係が見えない。
    # if n < 0 or len(A) <= n: return None
    if f > t: return None
    elif val == A[n]: return A[n]
    elif val > A[n]: return binary_search(A, n + 1, t, val)
    elif val < A[n]: return binary_search(A, f, n - 1, val)
A = [e for e in d if binary_search(b, 0, len(b) - 1, e) is not None]
print(len(A))

Submission status: Accepted

Solution code:
#! /usr/local/bin/python3
# coding: utf-8

from bisect import bisect_left

def search(S, y):
    pos = bisect_left(S, y)
    return S[pos] == y

def count(S, T):
    c = 0
    for y in T:
        if search(S, y):
            c += 1
    return c

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

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

print(count(S, T))

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

    count = 0

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

    print(count)

Submission status: Accepted

Solution code:
import sys

#f = open("input.txt", 'r')
f = sys.stdin
n = ''


n = f.readline().replace('\n','')
S = set(map(int, f.readline().replace('\n','').split()))
q = f.readline().replace('\n','')
T = set(map(int, f.readline().replace('\n','').split()))

print(len(S & T))

Submission status: Accepted

Solution code:
def binary_search(A, n, B, q):
    cnt = 0
    for i in range(q):
        left = 0
        right = n
        while left < right:
            mid = int((left + right) / 2)
            if A[mid] == B[i]:
                cnt += 1
                break
            elif B[i] < A[mid]:
                right = mid
            else:
                left = mid + 1
    return cnt

n = int(input())
A = list(map(int,input().split()))
q = int(input())
B = list(map(int,input().split()))
print(binary_search(A, n, B, q))

Submission status: Accepted

Solution code:
input()
s=set(map(int,input().split(" ")))
input()
t=set(map(int,input().split(" ")))
print(len(s&t))

Submission status: Accepted

Solution code:
def binSearch(l, x):
	u = 0
	d = len(l) - 1
	while True:
		if u > d:
			break
		m = int((u + d) / 2)
		if l[m] == x:
			return True
		elif l[m] < x:
			u = m + 1
		else:
			d = m - 1
	return False

n = int(input())
ni = [int(x) for x in input().split()]
q = int(input())
qi = [int(x) for x in input().split()]

print(sum([1 for x in qi if binSearch(ni, x) is True]))

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 = int((left + right)/2)
		if S[mid] == t:
			cnt += 1
			break
		elif t < S[mid]:
			right = mid
		else:
			left = mid + 1
		
print(cnt)

Submission status: Accepted

Solution code:
def binary_search(a, n, query):
    start = 0
    end = n - 1
    while start <= end:
        mean = (start + end) // 2
        if a[mean] == query:
            return True
        elif a[mean] > query:
            end = mean - 1 
        else:
            start = mean + 1
    
    return False


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 t:
    if binary_search(s, n, i):
        count += 1

print(count)

Submission status: Accepted

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


for i in listb:
    C=int(len(lista)/2)
    D=[0,len(lista)]
    while(1):
        if i<lista[C]:
            for k in D:
                if C>k:
                    d=k
                    break
            D.insert(0,C)
            C=int((C+d)/2)

        elif i>lista[C]:
            for k in D:
                if C<k:
                    d=k
                    break
            D.insert(0,C)
            C=int((C+d)/2)
        else:
            cnt+=1
            break
    
        if C==D[0]:
            break
    
        
print(cnt)

Submission status: Accepted

Solution code:
s = input()
snum = set(map(int, input().split()))
q = input()
qnum = set(map(int, input().split()))
print(len(snum & qnum))

Submission status: Accepted

Solution code:
n = int(input())
S = [int(l) for l in input().split(' ')]
kn = int(input())
T = [int(l) for l in input().split(' ')]

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

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

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 ele in t:
  i = bisect_left(s, ele)
  if s[i]==ele:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
input()
a=set(map(int,input().split()))
input()
b=set(map(int,input().split()))
print(len(a)-len(a-b))

Submission status: Accepted

Solution code:
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: Runtime Error

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


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

print(str(match_count))

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>

using namespace std;


int main() {
    
    long n;
    long q;
    cin >> n;
    vector <long> s;
    vector <long> t;
    for (int i=0;i<n;i++){
        long p;
        cin >> p;
        s.push_back(p);
    }
    cin >> q;
    for(int i=0;i<q;i++){
        long p;
        cin >> p;
        t.push_back(p);
    }
    vector <long>::iterator idx;
    long ans = 0;
    for (int i=0;i<q;i++) {
        idx = lower_bound(s.begin(), s.end(),t[i]);
        if(*idx == t[i]){
            ans += 1;
        }
    }
    cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
import copy
 
# 二分探索
def binearSearch(n, S, t):
     
    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 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 = linearSearch(n, copy.deepcopy(S), T[i])
         
        # 存在してたらカウント
        if isExist :
            C = C + 1
    # 出力
    print(C)

Submission status: Runtime Error

Solution code:
<?php
$lengthA = (int) fgets(STDIN);
$stdinA = explode(" ",fgets(STDIN));

$lengthKey = (int) fgets(STDIN);
$stdinKey = explode(" ",fgets(STDIN));

$count = 0;
for($j=0; $j<$lengthKey; ++$j){
    $result = BinarySearch($lengthA, $stdinA, $stdinKey[$j]);
    if($result == 1){
        $count++;
    }
}
echo $count . PHP_EOL;

function BinarySearch($N, $A, $key){
    $left = 0;
    $right = $N;
    while ($left < $right){
        //探索の範囲内の中央の要素を調べる
        $mid = ($left + $right) / 2;
        //目的のキーと中央の要素のキーが一致すれば探索を終了
        if ((int)$A[$mid] == (int)$key){
            return 1;
        }
        //前半部分を探索範囲とする
        if ($key < $A[$mid]){
            $right = $mid;
        }
        //後半部分を探索範囲とする
        else{
            $left = $mid + 1;
        }
    }
    return 0;
}
?>

Submission status: Runtime Error

Solution code:
# import sys

def binary_search(query, length, array):
	if length == 1:
		if query == array[0]:
			return 1
		else:
			return 0

	center = 2 / length
	if query > array[center]:
		return binary_search(query, length-(center+1), array[center+1:])
	elif query < array[center]:
		return binary_search(query, center, array[:center])
	else:
		return 1


n = int(raw_input())
S = map(int, raw_input().strip(" ").split(" "))
q = int(raw_input())
T = map(int, raw_input().strip(" ").split(" "))

count = 0

for t in T:
	count += binary_search(t, n, S)

print count

Submission status: Runtime Error

Solution code:
# import sys

def binary_search(query, length, array):
	if length == 1:
		if query == array[0]:
			return 1
		else:
			return 0

	center = length / 2
	if query > array[center]:
		return binary_search(query, length-(center+1), array[center+1:])
	elif query < array[center]:
		return binary_search(query, center, array[:center])
	else:
		return 1


n = int(raw_input())
S = map(int, raw_input().strip(" ").split(" "))
q = int(raw_input())
T = map(int, raw_input().strip(" ").split(" "))

count = 0

for t in T:
	count += binary_search(t, n, S)

print count

Submission status: Runtime Error

Solution code:
      
def binary_search(A,n):
    # sequence A, item n
    l = len(A)
    if l==0:
        return False
    elif A[l/2] > n:
        return binary_search(A[:l/2],n)
    elif A[l/2] == n:
        return True
    elif A[l/2]<n:
        return binary_search(A[(l/2)+1:],n)

n = int(raw_input())
S = set(map(int,raw_input().split()))
q = int(raw_input())
T = map(int,raw_input().split())

C = 0
for k in T:
    if binary_search(S,k):
        C += 1
print C

Submission status: Runtime Error

Solution code:
      
def binary_search(A,n,l):
    # sequence A, item n, l len(A)
    if l==0:
        return False
    elif A[l/2] > n:
        return binary_search(A[:l/2],n)
    elif A[l/2] == n:
        return True
    elif A[l/2]<n:
        return binary_search(A[(l/2)+1:],n)

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

l = len(S)
C = 0
for k in T:
    if binary_search(S,k,l):
        C += 1
print C

Submission status: Runtime Error

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B
# Binary Search
# Result:
import sys

NO_ANSWER = -1

def binary_sarch(target, ary, start, end):
    if start == end:
        if target == ary[start]:
            return start
        else:
            return NO_ANSWER

    mid = (start + end) / 2
    if target < ary[mid]:
        return binary_sarch(target, ary, start, mid - 1)
    elif target > ary[mid]:
        return binary_sarch(target, ary, mid + 1, end)
    else: # target == ary[mid]
        return mid


### main
ary_s_len = int(sys.stdin.readline().rstrip())
ary_s = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
ary_t_len = int(sys.stdin.readline().rstrip())
ary_t = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
assert len(ary_s) == ary_s_len
assert len(ary_t) == ary_t_len

count = 0
for e in ary_t:
    idx = binary_sarch(e, ary_s, 0, ary_s_len - 1)
    if idx >= 0:
        count += 1
print count

Submission status: Runtime Error

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

cnt = 0
cnt = 0
for ti in t:
	low = 0
	high = n - 1
	while low <= high:
		m = ( low+high )/2
		if ti < s[m]:
			high = m - 1
		elif s[m] < ti:
			low = m + 1
		else:
			cnt += 1
			break

print( cnt )

Submission status: Runtime Error

Solution code:
n = input()
S = map(int,raw_input().split())
m = input()
T = map(int,raw_input().split())
print len(T & S)

Submission status: Runtime Error

Solution code:
n = input()
S = set([int(s) for s in raw_input().split()])
m = input()
T = set([int(s) for s in raw_input().split()])

r=[]
def binarySearch(a=[],p=0):
	ll=0
	ul=len(a)
	
	while(True):
		if ll>ul:
			return -1
		ms=(int(ll)+int(ul))/2

		if a[i]==p:
			r.append(p)
		elif a[i]>p:
			ul=i-1
		else:
			ll=i+1






if __name__=="__main__":
	for i in T:
		binarySearch(S,i)

	print len(r)

Submission status: Runtime Error

Solution code:
n = input()
S = map(int,raw_input().split())
m = input()
T = map(int,raw_input().split())
print len(S&T)

Submission status: Runtime Error

Solution code:
n = input()
S = set(int(),raw_input().split())
m = input()
T = set(int(),raw_input().split())
print len(S&T)

Submission status: Runtime Error

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

def binary_search(A, 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

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

print(cnt)

Submission status: Runtime Error

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


def binarySearch(A, key):
    left, right = 0, 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

n = int(input())
S = [int(i) for i in range(n)]
q = int(input())
T = [int(i) for i in range(q)]

count = 0

for i in T:
    if (S,i):
        count += 1

print (count)

Submission status: Runtime Error

Solution code:
from collections import deque

iterator = [["NS", "S"], ["NT", "T"]]
var = {}

for i, j in iterator:
    var[i] = int(input())
    var[j] = [int(k) for k in input().split()]
var["S"] = sorted(var["S"])
var["T"] = sorted(var["T"])

dq = deque(var["S"])
res = 0

for T in var["T"]:
    if T in dq:
        res += 1
        while(dq[0] <= T):
            dq.popleft()
print(res)

Submission status: Runtime Error

Solution code:
def gost(lis,ky):
    
    lens=len(lis)
    
    if lens <= 5:
        if ky in lis:
            return True
        else:
            return False
    
    if ky <= lis[lens//2]:
        return gost(lis[:lens],ky)
    else:
        return gost(lis[lens:],ky)
    

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

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


i = 0
for it in t:
    if gost(s,it):
        i = i+1
print(i)

Submission status: Runtime Error

Solution code:
def gost(lis,ky):
    
    lens=len(lis)
    
    if lens <= 5:
        if ky in lis:
            return True
        else:
            return False
    
    if ky <= lis[lens//2]:
        return gost(lis[:lens/2],ky)
    else:
        return gost(lis[lens/2:],ky)
    

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

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


i = 0
for it in t:
    if gost(s,it):
        i = i+1
print(i)

Submission status: Runtime Error

Solution code:
def gost(lis,ky):
    
    lens=len(lis)
    
    if lens <= 5:
        print("key = "+str(ky)
        print(lis)
        if ky in lis:
            return True
        else:
            return False
    
    if ky <= lis[(lens//2)-1]:
        return gost(lis[:(lens//2)],ky)
    else:
        return gost(lis[(lens//2):],ky)
    

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

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


i = 0
for it in t:
    if gost(s,it):
        i = i+1
print(i)

Submission status: Runtime Error

Solution code:
n = input()

S = map(int, raw_input().split())

q = input()

T = map(int, raw_input().split())

S.append(0)
cnt = 0
for i in range(q):
    left = 0
    right = n
    while left < right:
        mid = (left + right) / 2
        if S[mid] == T[j]:
            cnt = cnt + 1
        else if T[j] < S[mid]:
            right = mid
        else:
            left = mid + 1

print cnt