Bài: ARRC – Tìm dãy C
Cho \(2\) dãy số nguyên đều gồm \(N\) phần tử là \(A_1, A_2, \dots, A_N\) và \(B_1, B_2, \dots, B_N\).
Dãy \(C\) bao gồm các phần tử chỉ xuất hiện ở một trong hai dãy \(A\) hoặc \(B\). Các phần tử trong dãy \(C\) đều phân biệt và được sắp xếp theo thứ tự tăng dần.
Yêu cầu: Cho \(2\) dãy \(A\) và \(B\), hãy tìm và in ra dãy \(C\).
Input
- Dòng đầu tiên gồm số nguyên dương \(N\) (\(1 \le N \le 10^5\)).
- Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^6\)).
- Dòng thứ ba gồm \(N\) số nguyên dương \(B_1, B_2, \dots, B_N\) (\(1 \le B_i \le 10^6\)).
Output
- Dòng thứ nhất in ra số lượng phần tử trong dãy \(C\). Nếu không có phần tử nào, in ra số 0.
- Dòng thứ hai in ra các phần tử trong dãy \(C\) theo thứ tự tăng dần, các số cách nhau bởi một khoảng trắng. (Nếu dãy \(C\) rỗng thì bỏ qua dòng này).
Ràng buộc
- Subtask 1 (60% số điểm): \(N \le 10^3\).
- Subtask 2 (40% số điểm): \(N \le 10^5\).
Example 1
Input
3
1 3 4
1 2 3
Output
2
2 4
Giải thích: Các phần tử xuất hiện ở cả hai dãy là \(1\) và \(3\). Phần tử chỉ xuất hiện ở một trong hai dãy là \(4\) (chỉ có ở \(A\)) và \(2\) (chỉ có ở \(B\)). Sắp xếp tăng dần ta được dãy \(C\) gồm \(2\) phần tử là 2 4.
Example 2
Input
4
1 1 1 1
2 2 2 2
Output
2
1 2
Giải thích: Phần tử \(1\) chỉ xuất hiện ở dãy \(A\), phần tử \(2\) chỉ xuất hiện ở dãy \(B\). Dãy \(C\) yêu cầu các phần tử phân biệt, do đó dãy \(C\) gồm \(2\) phần tử là 1 2.
Example 3
Input
5
1 2 3 4 5
5 4 3 2 1
Output
0
Giải thích: Tất cả các phần tử \(1, 2, 3, 4, 5\) đều xuất hiện ở cả hai dãy, không có phần tử nào chỉ xuất hiện ở một dãy. Do đó dãy \(C\) rỗng (có \(0\) phần tử).