Elearning CodePath – CTP Online Judge

Phép Toán Tập Hợp Trên Dãy Số

SET_OPERATIONS

🟢 Easy #General #Binary Search #Set / Map

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho hai dãy số nguyên $A = (A_1, A_2, \dots, A_M)$ và $B = (B_1, B_2, \dots, B_N)$.

Yêu cầu thực hiện hai nhiệm vụ sau:
1. **Giao của hai tập hợp ($A \cap B$):** Tìm các phần tử **thuộc cả hai dãy $A$ và $B$**, mỗi số chỉ tính một lần.
2. **Hiệu của hai tập hợp ($A \setminus B$):** Tìm các phần tử **thuộc dãy $A$ và không thuộc dãy $B$**, mỗi số chỉ tính một lần.

Kết quả phải được in ra theo **thứ tự xuất hiện lần đầu tiên** của chúng trong dãy $A$.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `DAYAB.INP`:

* Dòng 1: Ghi hai số nguyên dương $M$ và $N$ (độ dài của dãy $A$ và $B$).
* Dòng 2: Ghi $M$ số nguyên $A_1, A_2, \dots, A_M$.
* Dòng 3: Ghi $N$ số nguyên $B_1, B_2, \dots, B_N$.

Giới hạn:
* $M, N \le 5$ (Giả định rằng $5$ là $5 \times 10^5$ hoặc $5000$ vì ràng buộc quá nhỏ không hợp lý, ta sẽ dùng $10^5$ cho subtask).
* $|A_i|, |B_i| \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `DAYAB.OUT`:

* Dòng 1: Các phần tử thuộc $A \cap B$ theo thứ tự xuất hiện trong $A$, cách nhau bởi dấu cách.
* Dòng 2: Các phần tử thuộc $A \setminus B$ theo thứ tự xuất hiện trong $A$, cách nhau bởi dấu cách.

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- | :--- |
| 1 | $M, N \le 1000$ | $40\%$ | Duyệt $O(M \cdot N)$ (tìm kiếm tuyến tính $A_i$ trong $B$). |
| 2 | $M, N \le 10^5$ | $60\%$ | Sử dụng Hash Table/Set $O(M+N)$. |

---

✅ Đã AC: 0 / 0 submissions