Cerința

Se dă un vector x cu n elemente numere naturale, ordonate crescător, și un vector y cu m elemente, de asemenea numere naturale. Verificați pentru fiecare element al vectorului y dacă apare în x.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale vectorului x. Apoi și citește m și cele m elemente ale lui y.

Date de ieșire

Programul va afișa pe ecran m valori 0 sau 1, separate prin exact un spațiu. A j-a valoare afișată este 1, dacă al j-lea element al șirului y apare în x, respectiv 0 în caz contrar.

Restricții și precizări

• 1 ≤ n ≤ 25000
• 1 ≤ m ≤ 200000
• elementele celor 2 vectori vor fi mai mici decât 1.000.000.000

Exemplu

Intrare

7
1 2 5 6 9 10 14 
8
8 14 9 14 16 15 4 2 

Ieșire

0 1 1 1 0 0 0 1

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

bool gasesc(int elem, int a[], int st, int dr){
    if(st > dr)
        return 0;
    else{
        int mij = (st + dr) / 2;
        if(a[mij] == elem)
            return 1;
        else if(a[mij] < elem)
            return gasesc(elem, a, mij + 1, dr);
        else
            return gasesc(elem, a, st, mij - 1);
    }
}

/*
    while(st <= dr){
        int mij = (st + dr) / 2;
        if(a[mij] == val)
            return 1;
        else if(a[mij] < val)
            st = mij + 1;
        else
            dr = mij - 1;
    }
*/

int main()
{
    int n, m, a[25001], b[200001];
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    cin >> m;
    for(int i = 1; i <= m; ++i)
        cin >> b[i];
    for(int i = 1; i <= m; ++i)
        if(gasesc(b[i], a, 1, n))
            cout << 1 << ' ';
        else
            cout << 0 << ' ';
    return 0;
}