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

Solution code:
def binarysearch(ary, num):
    if len(ary) == 1 and ary[0] != num: return -1

    mid = len(ary) // 2

    if num < ary[mid]:
        return binarysearch(ary[:mid], num)
    elif num > ary[mid]:
        return binarysearch(ary[mid+1:], num)
    else:
        return ary[mid]

n = int(input())
s = list(map(lambda i: int(i), input().split(" ")))
q = int(input())
t = list(map(lambda i: int(i), input().split(" ")))
c = 0

for i in t:
    if binarysearch(s, i) != -1: c += 1

print(c)

Submission status: Runtime Error

Solution code:
import sys

#二分探索法のアルゴリズム構成
#1.真ん中の要素を選ぶ処理
#2.真ん中のデータと目的のデータを比較する処理
#3.探索の範囲を半分に狭める処理


if __name__ == '__main__':
    data = []
    count = 0
    #外部ファイル読み込み
    for line in sys.stdin:
        data.append(line.split())

    n = int(data[0][0])
    s = list(map(int, data[1]))
    q = int(data[2][0])
    t = list(map(int, data[3]))

    for i in range(0, q - 1):
        head = 0
        tail = n

        while True:
            center = len(s) // 2

            if s[center] == t[i] :
                count = count + 1
                print(t[i])
                break
            elif s[center] < t[i]:
                head = center + 1
            else :
                tail = center - 1

            s = s[head : tail + 1]

            if head >= tail :
                break

Submission status: Runtime Error

Solution code:
import sys

if __name__ == '__main__':
    data = []
    count = 0
    for line in sys.stdin:
        data.append(line.split())

    n = int(data[0][0])
    s = list(map(int, data[1]))
    q = int(data[2][0])
    t = list(map(int, data[3]))

    for i in range(0, q - 1):
        head = 0
        tail = n

        while True:
            center = len(s) // 2

            if s[center] == t[i] :
                count = count + 1
                print(t[i])
                break
            elif s[center] < t[i]:
                head = center + 1
            else :
                tail = center - 1

            s = s[head : tail + 1]

            if head >= tail :
                break

Submission status: Runtime Error

Solution code:
N = int(input())
S = list(set(map(int, input().split())))
S.sort()
Q = int(input())
T = list(map(int, input().split()))
ans = 0
for i in range(Q):
    OK = 0
    NG = N
    while abs(OK-NG)>1:
        mid = (OK+NG)//2
        if S[mid]<=T[i]:
            OK = mid
        else:
            NG = mid
    if S[OK] == T[i]:
        ans += 1

print(ans)

Submission status: Runtime Error

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


n = int(input())
s = [int(x) for x in input().split()]
q = int(input())
t = [int(x) for x in input().split()]
a = [x for x in t if binarySearch(s, x)]
print(len(a))

Submission status: Runtime Error

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

left=0
right=n
for i in range(t):
    while left<right:
        mid=(left+right)/2
        if s[mid]==t[i]:
            return cnt+=1
        elif s[mid]>t[i]:
            right=mid
        else:
            left=mid+1
            
            
print(cnt)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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(B)
c=(r+l)/2

n=0


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

print(n)

Submission status: Runtime Error

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(B)
c=(r+l)/2

n=0


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

print(n)

Submission status: Runtime Error

Solution code:
import bisect

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

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

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

n=0


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

print(n)

Submission status: Runtime Error

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(S)
c=(r+l)/2

n=0


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

print(n)

Submission status: Runtime Error

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

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

Solution code:
#include <iostream>
#include <sstream>

int main () {
  int n1,cnt=0;
  std::cin>>n1;
  int S[n1];
  for(int i=0;i<n1;i++){
    std::cin>>S[i];
  }
  int n2;
  std::cin>>n2;
  int T[n2];
  for(int i=0;i<n2;i++){
    std::cin>>T[i];
  }

  int left=0;
  int right=n1-1;
  int c,num;
  for(int i=0;i<n2;i++){
    num=T[i];
    left=0;
    right=n1-1;
    while(left<right){
      c=int((left+right)/2.0);
      if(S[c]>num){
	right=c;
      }
      if(S[c]<num){
	left=c+1;
      }
      if(S[c]==num){
	cnt++;
      }
    }
  }
  std::cout<<cnt<<'\n';
  return 0;
}

Submission status: Runtime Error

Solution code:
S=[]
T=[]
S_num=int(input())
S=input().split()
T_num=int(input())
T=input().split()
cnt=0

for i in T:
	print(i)
	right=S_num-1
	left=0
	center=int((right+left)/2)
	while left<=center and right>=center:
		if S[center]==T[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: Runtime Error

Solution code:
def binary_search(S,i,S_num)
	left=0
	right=
	while left<right:
		center=int((left+right)/2)
		if S[center]==i:
			return True
		elif S[center]>i:
			right=center-1
		elif S[center]<i:
			left=center+1
	return False

S=[]
T=[]
S_num=int(input())
S=input().split()
T_num=int(input())
T=input().split()
cnt=0

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

Submission status: Runtime Error

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]
cnt=0
low=0
t=(low+high)/2
high=len(b)
i=0
while(low<=high):
  if(b[i]==a[t]):
    i+=1
    cnt+=1
    break
  elif(i>a[t]):
    low=t+1
  elif(i<a[t]):
    high=t-1
  t=(low+high)/2
  
print(cnt)

Submission status: Runtime Error

Solution code:
#16D8103010K Ko Okasaki
#ALDS4_B

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

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

cnt=1

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

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

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

cnt=0

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

print(cnt

Submission status: Runtime Error

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 B[i]>c:
        l=c+1
        c=(r+l)/2
    elif B[i]<c:
        r=c
        c=(r+l)/2

print(n)

Submission status: Runtime Error

Solution code:
#16D8101014F 久留米 竜之介 2018/5/14
n=int(input())
S=list(map(int.input().split()))
q=int(input())
T=list(map(int,input().split()))
point=0
#print(S)
#print(T)

for i in T:
	left=0
	right=n
	while left < right:
		mid=int((left+right)/2)
		if S[mid] == i:
			point += 1
			break
		elif i < S[mid]:
			right = mid
		else:
			left = mid + 1
	#print(i,point)

print(point)

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
 
int A[1000000],n;
 
int main(){
    cin >> n;
    for(int i = 0;i < n;i++)
        scanf("%d",&A[i]);
         
    int q,k,sum = 0;
    cin >> q;
    for(int i = 0;i < q;i++){
        scanf("%d",&k);
        if(*lower_bound(A,A+n,k) == k)
            sum++;
    }
     
    cout << sum << endl;
     
    return 0;
}

Submission status: Runtime Error

Solution code:
include<iostream>
#include<vector>
std::vector<int> copy(std::vector<int> r,int s,int e){
  std::vector<int> res;
  for(int i=s;i<e;i++){
    res.push_back(r[i]);
  }
  return res;
}
 
bool binary_search(int v,std::vector<int> r){
  if(r.size()==0)return false;
  if(r.size()==1){
    if(v==r[0])return true;
    else return false;
  }
   
  int half=(int)(r.size()/2.0);
  if(r[half]==v)return true;
 
  if(r[half]>v)return binary_search(v,copy(r,0,half));
  else return binary_search(v,copy(r,half+1,r.size()));
}
 
i

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

print(len(set(s)&set(t))

Submission status: Runtime Error

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

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
		elif S[j+1]==S[j]:
			j+=1
				
print(cnt)

Submission status: Runtime Error

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[j+1]==T[j]:
			j+=1
			if T[i]==S[j]:
				cnt+=1
				break
		
print(cnt)

Submission status: Runtime Error

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
		while S[j+1]==S[j]:
			j+=1
		if T[i]==S[j]:
			cnt+=1
			break
		
print(cnt)

Submission status: Runtime Error

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):
		while S[j+1]==S[j]:
			j+=1
		if T[i]==S[j]:
			cnt+=1
			break
		
print(cnt)

Submission status: Runtime Error

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):
		while S[j+1]==S[j]&&j<n:
			j+=1
		if T[i]==S[j]:
			cnt+=1
			break
		
print(cnt)

Submission status: Runtime Error

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

for i in range(n-1):
	for j in range(i+1,n):
		if S[i]==S[j]:
			S.pop(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: Runtime Error

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

for i in range(n-1):
	for j in range(i+1,n):
		if S[i]==S[j]:
			S.pop(j)
print(S)

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

Submission status: Runtime Error

Solution code:

n = int(input())
S = input().split()
q = int(input())
T = input().split()
cnt = 0

for i in range(len(S)):
    S[i]=int(S[i])
for i in range(len(T)):
    T[i]=int(T[i])
for i in range(len(S)):
    x=0
    light=0
    reft=n
    while left<right and x==0:
        mid=int((left+right)/2)
        if S[mid]==T[i]:
            cnt+=1
            x+=1
        elif T[i]<S[mid]:
            right=mid
        else:
            left=mid+1
print(cnt)

Submission status: Runtime Error

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

for i in range(len(S)):
    S[i]=int(S[i])
for i in range(len(T)):
    T[i]=int(T[i])
for i in range(len(S)):
    x=0
    left=0
    right=n
    while left<right and x==0:
        mid=int((left+right)/2)
        if S[i]==T[mid]:
            cnt+=1
            x+=1
        elif S[i]<T[mid]:
            right=mid
        else:
            left=mid+1
print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np
import bisect

def bs(A, n):
    l=0
    r=len(A)
    while l<r:
        mid=int((l+r)/2)
        if A[mid]==n:
            return mid
        else:
            if n<A[mid]:
                r=mid
            else:
                l=mid+1

    return -1

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

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

A.sort()

cnt=0
for i in range(T):
    x=bs(A,B[i])
    if x!=(-1):
        cnt=cnt+1

print(cnt)

Submission status: Runtime Error

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(S) // 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: Runtime Error

Solution code:
def binarySearch(key, arr, N):
    left = 0
    right = N
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == key:
            return mid
        else if key < arr[mid]:
            right = mid
        else:
            left = mid + 1


N1 = int(input())
arr1 = [int(n) for n in input().split()]
N2 = int(input())
arr2 = [int(n) for n in input().split()]

print(sum([linearSearch(key, arr1) for key in arr2]))

Submission status: Runtime Error

Solution code:
def binarySearch(key, arr, N):
    left = 0
    right = N
    while left < right:
        mid = (left + right) // 2
        if arr[mid] == key:
            return mid
        else if key < arr[mid]:
            right = mid
        else:
            left = mid + 1


N1 = int(input())
arr1 = [int(n) for n in input().split()]
N2 = int(input())
arr2 = [int(n) for n in input().split()]

print(sum([binarySearch(key, arr1, N1) for key in arr2]))

Submission status: Runtime Error

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


N1 = int(input())
arr1 = [int(n) for n in input().split()]
N2 = int(input())
arr2 = [int(n) for n in input().split()]

print(sum([binarySearch(key, arr1, N1) for key in arr2]))

Submission status: Runtime Error

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

input()
s = set(input().split())
input()
t = set(input().split())
print(int(s & t))

Submission status: Runtime Error

Solution code:
a = [raw_input() for i in range(4)]
print len(set(a[1].split())&set(a[3].split())

Submission status: WA: Presentation 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,end="")