SEARCH1 - Tìm kiếm nhị phân 1

View as PDF
Submit solution
Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
Hieu Nguyen
Problem types
Allowed languages
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 xâu nhị phân độ dài ~m~, trong đó ký tự thứ ~i~ ~(1 ≤ i ≤ m)~ là 1 nếu ~b_i~ có xuất hiện trong dãy ~a_1, a_2, …, a_n~, và là 0 nếu ngược lại.

Sample

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

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

Comments

Please read the guidelines before commenting.


  • 0
    kietjumper  commented on July 4, 2025, 3:12 a.m. 
    #include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 7;
int a[N], b[N];
int x, y;

int bs(int a[], int n, int x){
    int g, d = 1, c = n, k = -1;
    while (d <= c){
        g = (d + c) / 2;
        if (x < a[g]) c = g - 1;
        else if (x > a[g]) d = g + 1;
        else{
            k = g;
            break;
        }
    }
    return k;
}

int main(){
    cin >> x >> y;
    for (int i = 1; i <= x; i++) cin >> a[i];
    for (int i = 1; i <= y; i++) cin >> b[i];
    for (int i = 1; i <= y; i++){
        if (bs(a, x, b[i]) != -1) cout << 1;
        else cout << 0;
    }
}



    Sol cho ae

  • -1
    AnhThu0704  commented on June 23, 2025, 1:24 p.m.

    b-bai~~ ney lem skao do~~~


  • -1
    AnhThu0704  commented on June 23, 2025, 1:23 p.m.

    helo mn


    • -1
      quynhmai1510  commented on June 23, 2025, 1:24 p.m.

      uk helo


      • -1
        AnhThu0704  commented on June 23, 2025, 1:24 p.m.

        pe le ai do


    • -1
      dongnhi13  commented on June 23, 2025, 1:23 p.m.

      uh chao


      • -1
        AnhThu0704  commented on June 23, 2025, 1:24 p.m.

        ei zaaaa


        • -1
          dongnhi13  commented on June 23, 2025, 1:25 p.m.

          uaa bak hok b-bit tui haa


  • -6
    super_god  commented on Oct. 8, 2024, 2:52 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.