Membership bằng std::binary_search

Bối cảnh

Một danh mục tĩnh chứa n mã số. Dữ liệu được nhập theo thứ tự bất kỳ nhưng sau khi nạp xong sẽ không thay đổi; hệ thống nhận nhiều truy vấn và mỗi truy vấn chỉ hỏi một câu rất cụ thể: mã x có tồn tại hay không. Đây là workload điển hình để sort dữ liệu một lần rồi dùng std::binary_search cho từng truy vấn. So với việc quét tuyến tính từ đầu đến cuối cho mỗi x, cách này tận dụng chi phí tiền xử lý để giảm thời gian truy vấn.

Homework Easy này không yêu cầu vị trí đầu tiên, số lần xuất hiện hay khoảng rank; vì vậy binary_search là công cụ vừa đủ. Điều quan trọng là nhớ precondition: range phải được sắp xếp theo đúng thứ tự mà thuật toán kỳ vọng. Nếu gọi trên dữ liệu ban đầu chưa sort, kết quả không đáng tin cậy.

Yêu cầu

1. Sort tăng dần.
2. Dùng std::binary_search cho q truy vấn.
3. In 1/0.

Input

Dòng 1 n; dòng 2 n số; dòng 3 q; q dòng x.

Output

q dòng 1 hoặc 0.

Ràng buộc

1≤n,q≤5000.

Ví dụ 1

Input

5
5 1 4 2 3
3
1
6
5

Output

1
0
1

Giải thích

Dữ liệu 5 1 4 2 3 được sort thành 1 2 3 4 5. Query 1 và 5 đều nằm trong range nên binary_search trả true, còn 6 lớn hơn mọi phần tử nên trả false. Vì output dùng 1/0, ba dòng lần lượt là 1, 0, 1.

Ví dụ 2

Input

1
0
2
0
1

Output

1
0

Giải thích

Dãy chỉ có số 0. Query 0 trùng phần tử duy nhất nên trả 1; query 1 không có nên trả 0. Ví dụ này kiểm tra n=1 và not-found mà không cần xử lý đặc biệt ngoài việc sort.

Thông tin học tập

• Module: M05
• Buổi: B16
• Loại bài: HOMEWORK
• Độ khó: Easy
• Concepts: std::sort, std::binary_search, membership
• Giới hạn kiến thức: B01-B16
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100