Employment
Contest: Codeforces Round 583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)
Difficulty rating: 2700
Tags: greedy, sortings

Two large companies "Cecsi" and "Poca Pola" are fighting against each other for a long time. In order to overcome their competitor, "Poca Pola" started a super secret project, for which it has total $$$n$$$ vacancies in all of their offices. After many tests and interviews $$$n$$$ candidates were selected and the only thing left was their employment.

Because all candidates have the same skills, it doesn't matter where each of them will work. That is why the company decided to distribute candidates between workplaces so that the total distance between home and workplace over all candidates is minimal.

It is well known that Earth is round, so it can be described as a circle, and all $$$m$$$ cities on Earth can be described as points on this circle. All cities are enumerated from $$$1$$$ to $$$m$$$ so that for each $$$i$$$ ($$$1 \le i \le m - 1$$$) cities with indexes $$$i$$$ and $$$i + 1$$$ are neighbors and cities with indexes $$$1$$$ and $$$m$$$ are neighbors as well. People can move only along the circle. The distance between any two cities equals to minimal number of transitions between neighboring cities you have to perform to get from one city to another. In particular, the distance between the city and itself equals $$$0$$$.

The "Poca Pola" vacancies are located at offices in cities $$$a_1, a_2, \ldots, a_n$$$. The candidates live in cities $$$b_1, b_2, \ldots, b_n$$$. It is possible that some vacancies are located in the same cities and some candidates live in the same cities.

The "Poca Pola" managers are too busy with super secret project, so you were asked to help "Poca Pola" to distribute candidates between workplaces, so that the sum of the distance between home and workplace over all candidates is minimum possible.

Input format:
The first line contains two integers $$$m$$$ and $$$n$$$ ($$$1 \le m \le 10^9$$$, $$$1 \le n \le 200\,000$$$) — the number of cities on Earth and the number of vacancies.

The second line contains $$$n$$$ integers $$$a_1, a_2, a_3, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — the cities where vacancies are located.

The third line contains $$$n$$$ integers $$$b_1, b_2, b_3, \ldots, b_n$$$ ($$$1 \le b_i \le m$$$) — the cities where the candidates live.

Output format:
The first line should contain the minimum total distance between home and workplace over all candidates.

The second line should contain $$$n$$$ different integers from $$$1$$$ to $$$n$$$. The $$$i$$$-th of them should be the index of candidate that should work at $$$i$$$-th workplace.

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

Note:
In the first example, the distance between each candidate and his workplace equals to $$$1$$$ (from $$$1$$$ to $$$10$$$, from $$$4$$$ to $$$5$$$ and from $$$6$$$ to $$$5$$$).

In the second example:

- The second candidate works at first workplace, the distance between cities $$$3$$$ and $$$1$$$ equals to $$$2$$$.
- The third candidate works at second workplace, the distance between cities $$$6$$$ and $$$4$$$ equals to $$$2$$$.
- The first candidate works at third workplace, the distance between cities $$$8$$$ and $$$8$$$ equals to $$$0$$$.

Example input:
10 3
1 5 5
10 4 6

Example output:
3
1 2 3

Example input:
10 3
1 4 8
8 3 6

Example output:
4
2 3 1

Editorial:
First, let's notice that the optimal answer can be achieved without changing the relative order of candidates. That means that if we order candidates by circle clockwise, the second candidate will work at the next clockwise workplace from the first candidate's workplace, the third candidate will work at the next clockwise workplace from the second candidate's workplace and so on. Let's prove it. If in optimal answer the order has changed, then there should be 2 candidates, so that the first of them lives earlier clockwise then the second and works at workplace, which is further. If we swap their workplaces, the distance between home and workplace for each of them will either stay the same or decrease. So, doing this swaps, we can achieve the situation, when the relative order of candidates stay the same.
Now we can come up with simple $$$O(n^2)$$$ solution. Let's first sort all candidates and workplaces by their city number. Let's select some workplace for the first candidate. Because in the optimal answer the order of candidates will not change, for each candidate we know his workplace. Now in $$$O(n)$$$ time we can calculate the total distance. And because there are $$$n$$$ possible workplaces for the first candidate, the solution works in $$$O(n^2)$$$ time.
To solve problem faster, let's notice, that if some candidate lives in city with number $$$x$$$ and his workplace has number $$$y$$$, the the total distance from home to work for him will be:
• $$$-x + y + m$$$ if $$$y < x - m / 2$$$
• $$$x - y$$$ if $$$x - m / 2 \le y < x$$$
• $$$-x + y$$$ if $$$x \le y < x + m / 2$$$
• $$$x - y + m$$$ if $$$x + m / 2 \le y$$$