Running in Pairs
Contest: Codeforces Round 592 (Div. 2)
Difficulty rating: 2400
Tags: constructive algorithms, greedy, math

Demonstrative competitions will be held in the run-up to the $$$20NN$$$ Berlatov Olympic Games. Today is the day for the running competition!

Berlatov team consists of $$$2n$$$ runners which are placed on two running tracks; $$$n$$$ runners are placed on each track. The runners are numbered from $$$1$$$ to $$$n$$$ on each track. The runner with number $$$i$$$ runs through the entire track in $$$i$$$ seconds.

The competition is held as follows: first runners on both tracks start running at the same time; when the slower of them arrives at the end of the track, second runners on both tracks start running, and everyone waits until the slower of them finishes running, and so on, until all $$$n$$$ pairs run through the track.

The organizers want the run to be as long as possible, but if it lasts for more than $$$k$$$ seconds, the crowd will get bored. As the coach of the team, you may choose any order in which the runners are arranged on each track (but you can't change the number of runners on each track or swap runners between different tracks).

You have to choose the order of runners on each track so that the duration of the competition is as long as possible, but does not exceed $$$k$$$ seconds.

Formally, you want to find two permutations $$$p$$$ and $$$q$$$ (both consisting of $$$n$$$ elements) such that $$$sum = \sum\limits_{i=1}^{n} max(p_i, q_i)$$$ is maximum possible, but does not exceed $$$k$$$. If there is no such pair, report about it.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^6, 1 \le k \le n^2$$$) — the number of runners on each track and the maximum possible duration of the competition, respectively.

Output format:
If it is impossible to reorder the runners so that the duration of the competition does not exceed $$$k$$$ seconds, print $$$-1$$$.

Otherwise, print three lines. The first line should contain one integer $$$sum$$$ — the maximum possible duration of the competition not exceeding $$$k$$$. The second line should contain a permutation of $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, all $$$p_i$$$ should be pairwise distinct) — the numbers of runners on the first track in the order they participate in the competition. The third line should contain a permutation of $$$n$$$ integers $$$q_1, q_2, \dots, q_n$$$ ($$$1 \le q_i \le n$$$, all $$$q_i$$$ should be pairwise distinct) — the numbers of runners on the second track in the order they participate in the competition. The value of $$$sum = \sum\limits_{i=1}^{n} max(p_i, q_i)$$$ should be maximum possible, but should not exceed $$$k$$$. If there are multiple answers, print any of them.

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

Note:
In the first example the order of runners on the first track should be $$$[5, 3, 2, 1, 4]$$$, and the order of runners on the second track should be $$$[1, 4, 2, 5, 3]$$$. Then the duration of the competition is $$$max(5, 1) + max(3, 4) + max(2, 2) + max(1, 5) + max(4, 3) = 5 + 4 + 2 + 5 + 4 = 20$$$, so it is equal to the maximum allowed duration.

In the first example the order of runners on the first track should be $$$[2, 3, 1]$$$, and the order of runners on the second track should be $$$[2, 1, 3]$$$. Then the duration of the competition is $$$8$$$, and it is the maximum possible duration for $$$n = 3$$$.

Example input:
5 20

Example output:
20
1 2 3 4 5 
5 2 4 3 1

Example input:
3 9

Example output:
8
1 2 3 
3 2 1

Editorial:
First of all, let's understand which values of $$$sum$$$ we can obtain at all. Obviously, the minimum possible value of $$$sum$$$ is $$$mn = \frac{n(n+1)}{2}$$$. The maximum possible value of $$$sum$$$ is $$$mx = (\lceil\frac{n}{2}\rceil + 1 + n) \cdot \lfloor\frac{n}{2}\rfloor + n \% 2 \cdot \lceil\frac{n}{2}\rceil$$$. We can obtain every possible value of $$$sum$$$ between $$$mn$$$ and $$$mx$$$ and we will show how to do it below.
If $$$k < mn$$$ then the answer is -1 (and this is the only such case). Otherwise, the answer exists and we need to construct it somehow. Firstly, suppose that the first permutation is identic permutation ($$$1, 2, \dots, n$$$) and the only permutation we change is the second one. Initially, the second permutation is also identic. Now we have $$$sum = mn$$$ and we need to change it to $$$sum = k$$$ or to the maximum possible number not greater than $$$k$$$. To do that, let's learn how to increase $$$sum$$$ by one. Let's see what will happen if we swap $$$n$$$ and $$$n-1$$$. Then the value of $$$sum$$$ will increase by one. If we swap $$$n$$$ and $$$n-2$$$ then the value of $$$sum$$$ will increase by $$$2$$$, and so on. If we swap $$$n$$$ and $$$1$$$ then the value of $$$sum$$$ will increase by $$$n-1$$$.
So, the following constructive algorithm comes to mind: let's carry the current segment of permutation $$$[l; r]$$$ we can change (it is always segment because after some swaps some leftmost and rightmost elements cannot increase our answer because they're will be already placed optimally) and the value $$$add$$$ we need to add to $$$sum$$$ to obtain the maximum possible sum not greater than $$$k$$$. Initially $$$l=1, r=n, add = k - mn$$$. Now let's understand the maximum value by which we can increase the value of $$$sum$$$. Now it is $$$r-l$$$. If this value is greater than $$$add$$$ then let's swap $$$p_r$$$ and $$$p_{r - add}$$$, and break the cycle ($$$p$$$ is the second permutation). Otherwise, let's swap $$$p_l$$$ and $$$p_r$$$, decrease $$$add$$$ by $$$r-l$$$ and set $$$l := l + 1, r := r - 1$$$ . If at some moment $$$l$$$ becomes greater than or equal to $$$r$$$ then break the cycle.
Now we got the second permutation $$$p$$$ with the maximum possible value of $$$sum$$$ not greater than $$$k$$$, we can calculate the numeric answer (or print $$$min(mx, k)$$$), print identic permutation and the permutation $$$p$$$.