Divan and a New Project  (Codeforces 1614B)
Tags: Others, sortings

The company "Divan's Sofas" is planning to build $$$n + 1$$$ different buildings on a coordinate line so that:   the coordinate of each building is an integer number;  no two buildings stand at the same point. Let $$$x_i$$$ be the coordinate of the $$$i$$$-th building. To get from the building $$$i$$$ to the building $$$j$$$, Divan spends $$$|x_i - x_j|$$$ minutes, where $$$|y|$$$ is the absolute value of $$$y$$$.All buildings that Divan is going to build can be numbered from $$$0$$$ to $$$n$$$. The businessman will live in the building $$$0$$$, the new headquarters of "Divan's Sofas". In the first ten years after construction Divan will visit the $$$i$$$-th building $$$a_i$$$ times, each time spending $$$2 \cdot |x_0-x_i|$$$ minutes for walking.Divan asks you to choose the coordinates for all $$$n + 1$$$ buildings so that over the next ten years the businessman will spend as little time for walking as possible.

Input: Each test contains several test cases. The first line contains one integer number $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.The first line of each case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of buildings that "Divan's Sofas" is going to build, apart from the headquarters.The second line contains the sequence $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$), where $$$a_i$$$ is the number of visits to the $$$i$$$-th building.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, on the first line print the number $$$T$$$ — the minimum time Divan will spend walking. On the second line print the sequence $$$x_0, x_1, \ldots, x_n$$$ of $$$n + 1$$$ integers, where $$$x_i$$$ ($$$-10^6 \le x_i \le 10^6$$$) is the selected coordinate of the $$$i$$$-th building. It can be shown that an optimal answer exists with coordinates not exceeding $$$10^6$$$.If there are multiple answers, print any of them.

Note: Let's look at the first example.Divan will visit the first building $$$a_1 = 1$$$ times, the second $$$a_2 = 2$$$ times and the third $$$a_3 = 3$$$ times. Then one of the optimal solution will be as follows:   the headquarters is located in $$$x_0 = 2$$$;  $$$x_1 = 4$$$: Divan will spend $$$2 \cdot |x_0-x_1| \cdot a_1 = 2 \cdot |2-4| \cdot 1 = 4$$$ minutes walking to the first building;  $$$x_2 = 1$$$: Divan will spend $$$2 \cdot |x_0-x_2| \cdot a_2 = 2 \cdot |2-1| \cdot 2 = 4$$$ minutes walking to the second building;  $$$x_3 = 3$$$: Divan will spend $$$2 \cdot |x_0-x_3| \cdot a_3 = 2 \cdot |2-3| \cdot 3 = 6$$$ minutes walking to the third building. In total, Divan will spend $$$4 + 4 + 6 = 14$$$ minutes. It can be shown that it is impossible to arrange buildings so that the businessman spends less time.Among others, $$$x = [1, 3, 2, 0]$$$, $$$x = [-5, -3, -6, -4]$$$ are also correct answers for the first example.

Sample Inputs:
4
3
1 2 3
5
3 8 10 6 1
5
1 1 1 1 1
1
0

Sample Outputs:
14
2 4 1 3
78
1 -1 0 2 3 4
18
3 6 1 5 2 4
0
1 2

Solution (Python):
import sys, io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def new_project(n, a):
    t = 0
    x = [0] * (n + 1)
    a = sorted(zip(a, range(1, n + 1)), key=lambda x: -x[0])
    pos = 1
    for (ai, idx) in a:
        t += 2 * ai * abs(pos)
        x[idx] = pos
        if pos >= 0:
            pos *= -1
        else:
            pos = pos * -1 + 1
    sys.stdout.write(f'{t}\n')
    sys.stdout.write(f"{' '.join(map(str, x))}\n")
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    new_project(n, a)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    assert len(a) == n
    x = [0] * n
    coord = 1
    total = 0
    for (i, c) in sorted(enumerate(a), key=lambda t: t[1], reverse=True):
        total += abs(coord) * c * 2
        x[i] = coord
        if coord > 0:
            coord = -coord
        else:
            coord = -coord + 1
    print(total)
    print(0, ' '.join(map(str, x)))

Solution (Python):
def solve():
    n = int(input())
    a = list(map(int, input().split()))
    a = zip(a, range(1, n + 1))
    a = sorted(a, reverse=True)
    ans = [0] * (n + 1)
    (cur, tot) = (1, 0)
    for (v, idx) in a:
        ans[idx] = cur
        tot += v * 2 * abs(cur)
        if cur > 0:
            cur = -1 * cur
        else:
            cur = abs(cur) + 1
    print(tot)
    print(' '.join(map(str, ans)))
for i in range(int(input())):
    solve()