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], \ldots, A[N-1]$ and the numbers in the second array
are $B[0], B[1], \ldots, B[N-1]$. The numbers in both arrays are in increasing order, that is,
* $A[0] \le A[1] \le \ldots \le A[N-1]$, and
* $B[0] \le B[1] \le \ldots \le 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$.

Implementation Details

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.

Examples

Example 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]$.

Example 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]$.

Constraints

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

Sample Grader

The sample grader reads the input in the following format:

• line $1$: $N$
• line $2$: $A[0] \; A[1] \; \ldots \; A[N-1]$
• line $3$: $B[0] \; B[1] \; \ldots \; B[N-1]$

Let the elements of the array returned by smallest_sums be $c[0], c[1], \ldots, c[n-1]$ for some non-negative $n$. The output of the sample grader is in the following format:
* line $1$: $c[0] \; c[1] \; \ldots \; c[n-1]$

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (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], \ldots, A[N-1]$ and the numbers in the second array
are $B[0], B[1], \ldots, B[N-1]$. The numbers in both arrays are in increasing order, that is,
* $A[0] \le A[1] \le \ldots \le A[N-1]$, and
* $B[0] \le B[1] \le \ldots \le 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$.

Implementation Details

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.

Examples

Example 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]$.

Example 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]$.

Constraints

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

Sample Grader

The sample grader reads the input in the following format:

• line $1$: $N$
• line $2$: $A[0] \; A[1] \; \ldots \; A[N-1]$
• line $3$: $B[0] \; B[1] \; \ldots \; B[N-1]$

Let the elements of the array returned by smallest_sums be $c[0], c[1], \ldots, c[n-1]$ for some non-negative $n$. The output of the sample grader is in the following format:
* line $1$: $c[0] \; c[1] \; \ldots \; c[n-1]$

Execution limits

Your solution will have 1.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "aplusb.h"

std::vector<int> smallest_sums(int N, std::vector<int> A, std::vector<int> B) {
    return {};
}

参考函数签名

#include "aplusb.h"

std::vector<int> smallest_sums(int N, std::vector<int> A, std::vector<int> B) {
    return {};
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include "aplusb.h"

std::vector<int> smallest_sums(int N, std::vector<int> A, std::vector<int> B) {
return {};
}