Trộn hai dãy đã sắp xếp

Buổi 06 — Sắp xếp & Tìm kiếm sorting
Points
19
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Cho hai dãy số nguyên $A$ (gồm $N$ phần tử) và $B$ (gồm $M$ phần tử) đều đã được sắp xếp theo thứ tự không giảm. Hãy dùng kỹ thuật hai con trỏ để trộn hai dãy thành một dãy duy nhất có $N + M$ phần tử cũng được sắp xếp không giảm trong thời gian $O(N + M)$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$. Dòng thứ hai chứa $N$ số nguyên của dãy $A$. Dòng thứ ba chứa $M$ số nguyên của dãy $B$.

Dữ liệu ra

Một dòng chứa $N + M$ số nguyên sau khi trộn.

Ví dụ
Input Output
3 4\n1 4 7\n2 3 7 9 1 2 3 4 7 7 9
2 2\n10 20\n1 2 1 2 10 20
Giới hạn

$1 \le N, M \le 10^5$, $|A_i|, |B_j| \le 10^9$.

Draft saved