Christmas Trees
Contest: Codeforces Round 611 (Div. 3)
Difficulty rating: 1800
Tags: graphs, greedy, shortest paths

There are $$$n$$$ Christmas trees on an infinite number line. The $$$i$$$-th tree grows at the position $$$x_i$$$. All $$$x_i$$$ are guaranteed to be distinct.

Each integer point can be either occupied by the Christmas tree, by the human or not occupied at all. Non-integer points cannot be occupied by anything.

There are $$$m$$$ people who want to celebrate Christmas. Let $$$y_1, y_2, \dots, y_m$$$ be the positions of people (note that all values $$$x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$$$ should be distinct and all $$$y_j$$$ should be integer). You want to find such an arrangement of people that the value $$$\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$$$ is the minimum possible (in other words, the sum of distances to the nearest Christmas tree for all people should be minimized).

In other words, let $$$d_j$$$ be the distance from the $$$j$$$-th human to the nearest Christmas tree ($$$d_j = \min\limits_{i=1}^{n} |y_j - x_i|$$$). Then you need to choose such positions $$$y_1, y_2, \dots, y_m$$$ that $$$\sum\limits_{j=1}^{m} d_j$$$ is the minimum possible.

Input format:
The first line of the input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — the number of Christmas trees and the number of people.

The second line of the input contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$-10^9 \le x_i \le 10^9$$$), where $$$x_i$$$ is the position of the $$$i$$$-th Christmas tree. It is guaranteed that all $$$x_i$$$ are distinct.

Output format:
In the first line print one integer $$$res$$$ — the minimum possible value of $$$\sum\limits_{j=1}^{m}\min\limits_{i=1}^{n}|x_i - y_j|$$$ (in other words, the sum of distances to the nearest Christmas tree for all people).

In the second line print $$$m$$$ integers $$$y_1, y_2, \dots, y_m$$$ ($$$-2 \cdot 10^9 \le y_j \le 2 \cdot 10^9$$$), where $$$y_j$$$ is the position of the $$$j$$$-th human. All $$$y_j$$$ should be distinct and all values $$$x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_m$$$ should be distinct.

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 6
1 5

Example output:
8
-1 2 6 4 0 3

Example input:
3 5
0 3 1

Example output:
7
5 -2 4 -1 2

Editorial:
In this problem, we first need to consider all points adjacent to at least one Christmas tree, then all points at the distance two from the nearby Christmas tree and so on... What it looks like? Yes, well-known multi-source bfs.
Let's maintain a queue of positions and the set of used positions (and the distance to each vertex, of course). In the first step, we add all positions of the Christmas tree with a zero distance as initial vertices. Let the current vertex is $$$v$$$. If $$$d_v = 0$$$ (this is the Christmas tree) then just add $$$v-1$$$ and $$$v+1$$$ to the queue (if these vertices aren't added already) and continue. Otherwise, increase the answer by $$$d_v$$$ and add $$$v$$$ to the array of positions of people. When the length of this array reaches $$$m$$$, interrupt bfs and print the answer.
Don't forget about some special cases as using Arrays.sort in Java or using std::unordered_map in C++ because this can lead to the quadratic complexity.
Time complexity: $$$O(n \log n)$$$.