29739번 - A Plus B 서브태스크다국어언어 제한함수 구현

문제

Borcsa has two arrays, each of them containing $N$ non-negative integers.

The numbers in the first array are $A[0],A[1], \dots ,A[N - 1]$ and the numbers in the second array are $B[0],B[1], \dots ,B[N - 1]$. The numbers in both arrays are in increasing order, that is,

• $A[0] ≤ A[1] ≤ \dots ≤ A[N - 1],ドル and
• $B[0] ≤ B[1] ≤ … ≤ B[N - 1]$.

Borcsa really likes arithmetical addition, so for each $i$ from 0ドル$ to $N - 1$ and for each $j$ from 0ドル$ to $N - 1,ドル inclusive, she computed the sum $A[i] + B[j]$.

Let array $C$ contain all $N^2$ sums computed by Borcsa, sorted in increasing order. Your task is to find the first $N$ values in $C$.

구현

You should implement the following procedure:

int[] smallest_sums(int N, int[] A, int[] B)

• $N$: the number of elements in each array.
• $A,ドル $B$: arrays of length $N$ containing non-negative integers sorted in increasing order.
• This procedure should return an array of length $N$ containing the $N$ smallest sums obtained by adding an element from $A$ and an element from $B$. The array should contain the sums in increasing order.
• This procedure is called exactly once for each test case.

예제 1

Consider the following call:

smallest_sums(2, [0, 2], [1, 4])

In this case, $N = 2$. There are $N^2 = 4$ sums computed by Borcsa:

• 0ドル + 1 = 1$
• 0ドル + 4 = 4$
• 2ドル + 1 = 3$
• 2ドル + 4 = 6$

Array $C$ contains these sums sorted in increasing order, that is, $C = [1, 3, 4, 6]$. The $N = 2$ smallest elements in C are 1ドル$ and 3ドル$. Therefore, the procedure should return the array $[1, 3]$.

예제 2

Consider the following call:

smallest_sums(3, [0, 2, 2], [3, 5, 6])

The 9ドル$ pairwise sums (in increasing order) are 3,ドル 5, 5, 5, 6, 7, 7, 8, 8$. The procedure should return the 3ドル$ smallest sums, that is, the array $[3, 5, 5]$.

입력

출력

제한

• 1ドル ≤ N ≤ 100,000円$
• 0ドル ≤ A[i] ≤ 10^9$ (for each $i$ such that 0ドル ≤ i < N$)
• 0ドル ≤ B[i] ≤ 10^9$ (for each $i$ such that 0ドル ≤ i < N$)
• $A$ and $B$ are sorted in increasing order.

서브태스크

노트

샘플 그레이더

The sample grader reads the input in the following format:

• line 1ドル$: $N$
• line 2ドル$: $A[0]$ $A[1]$ $\dots$ $A[N - 1]$
• line 3ドル$: $B[0]$ $B[1]$ $\dots$ $B[N - 1]$

Let the elements of the array returned by smallest_sums be $c[0], c[1], \dots , c[n - 1]$ for some nonnegative $n$. The output of the sample grader is in the following format:

• line 1ドル$: $c[0]$ $c[1]$ $\dots$ $c[n - 1]$

첨부

• aplusb.zip