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, 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
unordered_map là full
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.
có 2 cách, 1 là dùng sort+binary_search,2 là dùng map lưu lại giá trị xuất hiện nhỏ nhất của a[i] rồi xuất kq ra thôi