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ả:
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~. 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

Please read the guidelines before commenting.


  • 0
    lehuusang5a1  đã bình luận lúc 12, Tháng 4, 2026, 13:58

    có ai code duoc phuong phap tìm kiếm tuần tự mà full ac không cho mình xin code voi pls😢


  • 0
    nguyendinhdunggn  đã bình luận lúc 31, Tháng 3, 2026, 16:14

    include <bits/stdc++.h>

    using namespace std; int main(){ ios::syncwithstdio(false); cin.tie(nullptr); int n,m; cin>>n>>m; vector<long long>a(n),b(m); for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<m;i++)cin>>b[i]; vector<pair<long long,int>>arr; arr.reserve(n); for(int i=0;i<n;i++)arr.pushback({a[i],i+1}); sort(arr.begin(),arr.end()); for(int i=0;i<m;i++){ auto it=lowerbound(arr.begin(),arr.end(),make_pair(b[i],0)); if(it!=arr.end()&&it->first==b[i])cout


  • 1
    kietjumper  đã bình luận lúc 22, Tháng 1, 2026, 16:01 ← sửa 2

    map

    #include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    unordered_map< int, int > pos;

    for (int i = 0; i < n; ++i) 
    {
        cin >> a[i];
        if (pos.count(a[i]) == 0) 
        {
            pos[a[i]] = i + 1; 
        }
    }

    for (int i = 0, x; i < m; ++i) 
    {
        cin >> x;
        cout << (pos.count(x) ? pos[x] : 0) << " ";
    }

    return 0;
}

  • 0
    thien_365  đã bình luận lúc 4, Tháng 6, 2025, 15:52

    chặt nhị phân vẫn ra nha bạn


  • 0
    hhieu474  đã bình luận lúc 17, Tháng 11, 2024, 8:04

    unordered_map là full


    • -1
      thien_365  đã bình luận lúc 4, Tháng 6, 2025, 15:52

      còn cách tknp nữa nha bạn


  • 0
    vuonghao  đã bình luận lúc 15, Tháng 10, 2024, 13:32

    Bài này cho chỉ cần tìm kiếm trên map là ok


  • 0
    zangvu  đã bình luận lúc 6, Tháng 10, 2024, 5:48

    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


  • 0
    tiennv  đã bình luận lúc 2, Tháng 10, 2024, 11:13

    bài này dùng unordered_map thì oke


  • 0
    tungkq123  đã bình luận lúc 18, Tháng 2, 2024, 12:27

    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


  • 0
    vuonghao  đã bình luận lúc 5, Tháng 9, 2023, 2:34

    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.