SEARCH3 - Tìm kiếm nhị phân 3
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, 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~. 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
6 4 7 2 4 1 3
3 1 5 4 8
Output #1
7 6 0 2 0
Problem source: Chuyên Sơn La Online Judge
Bình luận
bai nay unordered_map la ok sao ten lai la tim kiem nhi phan hack nao the
chặt nhị phân vẫn ra nha bạn
unordered_map là full
còn cách tknp nữa nha bạn
Bài này cho chỉ cần tìm kiếm trên map là ok
chặt trên pair nhá mấy ní p.first lưu giá trị, p.second lưu vị trí gốc r chặt trên p.first là ok
bài này dùng unordered_map thì oke
bạn ơi ai, bi <= 10 * 9 ko map dc đâu, bài này dùng sort và tk nhị phân phần tử xh đầu nhé. test case cho 10 * 9 là cách của bạn bị tràn mảng
có bạn nào giải bài này chưa cho mình xin code với. Test có vấn đề gì không sao mình toàn bị WA ở test 2.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.