SEARCH2 - Tìm kiếm nhị phân 2

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 dòng duy nhất chứa ~m~ số nguyên, trong đó số thứ ~i~ ~(1 ≤ i ≤ m)~ là chỉ số ~j~ nhỏ nhất mà ~a_j = b_i~ (nếu tồn tại) và là ~0~ nếu ngược lại. Hai số liên tiếp được ghi cách nhau một dấu cách.

Sample

Input #1
7 5
1 2 3 4 4 6 7
3 1 5 4 8
Output #1
3 1 0 4 0

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


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • -3
    ananan2q  đã bình luận lúc 27, Tháng 2, 2024, 15:37

    nhu chubin


  • -5
    ananan2q  đã bình luận lúc 27, Tháng 2, 2024, 15:34

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • 3
      haidang3004  đã bình luận lúc 27, Tháng 2, 2024, 16:49

      ko ac đc nên cay ah