Tìm kiếm nhị phân 2 - LCOJ: Luyện Code Online Judge

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

Đ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~ 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

Please read the guidelines before commenting.

-2

giúp tui với #include <bits/stdc++.h> using namespace std;

int main() { int n,m; cin>>n>>m; vector<long long>a(n),b(m); set<long long>s;

for(int i=0;i&lt;n;i++)
{
    cin>>a[i];
    s.insert(a[i]);
}

for(int i=0;i&lt;m;i++)
{
    cin>>b[i];
}

for(int i=0;i&lt;m;i++)
{
    if(s.count(b[i])==0) {
        cout << 0;
    }
    else {
        for(int j=0;j&lt;n;j++)
        {
            if(a[j]==b[i]) {
                cout << j+1;
                break;
            }
        }
    }
    if(i+1&lt;m) cout<<" ";
}
return 0;

} code này bị sai ở test 4 bị tle