Tìm kiếm nhị phân 1 - LCOJ: Luyện Code Online Judge

SEARCH1 - Tìm kiếm nhị phân 1

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho hai dãy số nguyên ~a_1, a_2, …, a_n~ và ~b_1, b_2, …, b_m~ trong đó dãy số ~a_1, a_2, …, a_n~ đã được sắp xếp không giảm (tức là ~a_1 ≤ a_2 ≤ … ≤ a_n~). Với mỗi chỉ số ~i~ ~(1 ≤ i ≤ m)~ hãy tìm sự xuất hiện của ~b_i~ trong dãy ~a_1, a_2, …, a_n~.

Input

Dòng đầu ghi hai số nguyên dương ~n~ và ~m~;
Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, …, a_n~;
Dòng thứ ba ghi ~m~ số nguyên ~b_1, b_2, …, b_m~.

Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.

Giới hạn:

~1 ≤ n, m ≤ 10^5; |a_i|, |b_i| ≤ 10^9~.

Output

Một xâu nhị phân độ dài ~m~, trong đó ký tự thứ ~i~ ~(1 ≤ i ≤ m)~ là 1 nếu ~b_i~ có xuất hiện trong dãy ~a_1, a_2, …, a_n~, và là 0 nếu ngược lại.

Sample

Input #1

7 5
1 2 3 4 4 6 7
3 1 5 4 8

Output #1

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

0

nguyendinhdunggn đã bình luận lúc 1, Tháng 4, 2026, 15:57

include<bits/stdc++.h>

using namespace std; int n,m,i,l,r,mid; long long a[100001],b[100001]; int main(){ cin>>n>>m; for(i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); for(i=1;i<=m;i++)cin>>b[i]; for(i=1;i<=m;i++){ l=1;r=n;bool ok=0; while(l<=r){ mid=l+(r-l)/2; if(a[mid]==b[i]){ok=1;break;} else if(a[mid]<b[i])l=mid+1; else r=mid-1; } cout<<ok; } return 0; }