Trộn Cân Xe Cảng Vạn Tỉ

Mô tả

Cảng biển Vạn Tỉ là đầu mối giao thương tấp nập bậc nhất vùng duyên hải miền Trung. Mỗi ngày, hàng trăm xe tải chở container luân chuyển qua hai trạm cân tự động: trạm A ở cổng phía Bắc và trạm B ở cổng phía Nam. Mỗi trạm đều ghi lại trọng lượng xe (tính theo tấn) và xuất ra một danh sách đã được sắp xếp tăng dần từ nhẹ tới nặng.

Cuối ca, nhân viên vận hành cần tổng hợp dữ liệu từ cả hai trạm thành một danh sách duy nhất, cũng theo thứ tự từ nhẹ đến nặng. Trọng số của mỗi trạm khá lớn nên việc đổ hết vào một danh sách rồi sắp xếp lại tốn khá nhiều thời gian. Bạn được giao nhiệm vụ viết chương trình trộn hai danh sách đã sắp xếp này thành một danh sách kết quả tăng dần, tận dụng tối đa thứ tự sẵn có để thao tác nhanh nhất.

Đầu vào

• Dòng đầu chứa số nguyên n — số lượng xe ghi nhận ở trạm A (1 ≤ n ≤ 10^5).
• Dòng thứ hai chứa n số nguyên cách nhau bởi khoảng trắng — trọng lượng xe trạm A, sắp xếp tăng dần không giảm.
• Dòng thứ ba chứa số nguyên m — số lượng xe ghi nhận ở trạm B (1 ≤ m ≤ 10^5).
• Dòng thứ tư chứa m số nguyên cách nhau bởi khoảng trắng — trọng lượng xe trạm B, sắp xếp tăng dần không giảm.

Đầu ra

• In ra một dòng duy nhất gồm n + m số nguyên cách nhau bởi khoảng trắng — trọng lượng tất cả xe theo thứ tự tăng dần không giảm.

Ràng buộc

• 1 ≤ n, m ≤ 10^5.
• Mỗi trọng lượng xe là số nguyên dương, nằm trong khoảng [1, 10^6].
• Tổng số phần tử kết quả n + m ≤ 2 × 10^5.
• Các mảng đầu vào đã được sắp xếp tăng dần không giảm (có thể có giá trị trùng lặp).

Ví dụ

Ví dụ 1:

Dòng đầu vào: 3 5 10 15 4 2 8 12 20

Kết quả: 2 5 8 10 12 15 20

Giải thích từng bước:

• Trạm A: [5, 10, 15], Trạm B: [2, 8, 12, 20].
• So sánh 5 và 2 → lấy 2. Kết quả: [2].
• So sánh 5 và 8 → lấy 5. Kết quả: [2, 5].
• So sánh 10 và 8 → lấy 8. Kết quả: [2, 5, 8].
• So sánh 10 và 12 → lấy 10. Kết quả: [2, 5, 8, 10].
• So sánh 15 và 12 → lấy 12. Kết quả: [2, 5, 8, 10, 12].
• So sánh 15 và 20 → lấy 15. Kết quả: [2, 5, 8, 10, 12, 15].
• Trạm A hết → lấy phần còn lại của trạm B: [20]. Kết quả cuối: [2, 5, 8, 10, 12, 15, 20].

Ví dụ 2:

Dòng đầu vào: 2 7 7 3 3 7 9

Kết quả: 3 7 7 7 9

Giải thích: Các xe có trọng lượng trùng nhau (7 tấn xuất hiện ở cả hai trạm) đều được giữ lại trong kết quả, thứ tự ổn định.