SEARCH1 - Tìm kiếm nhị phân 1
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, 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à
1nếu ~b_i~ có xuất hiện trong dãy ~a_1, a_2, …, a_n~, và là0nếu ngược lại.
Sample
Input #1
7 5
1 2 3 4 4 6 7
3 1 5 4 8
Output #1
11010
Problem source: Chuyên Sơn La Online Judge
Bình luận
hello ae