Optimal Number Permutation (Codeforces 622D)
Tags: Others, constructive algorithms

You have array a that contains all integers from 1 to n twice. You can arbitrary permute any numbers in a.Let number i be in positions xi, yi (xi < yi) in the permuted array a. Let's define the value di = yi - xi — the distance between the positions of the number i. Permute the numbers in array a to minimize the value of the sum .

Input: The only line contains integer n (1 ≤ n ≤ 5·105).

Output: Print 2n integers — the permuted array a that minimizes the value of the sum s.


Sample Inputs:
2

1

Sample Outputs:
1 1 2 2

1 1

Solution (Python):
n = int(input())
s = []
for i in range(1, n + 1, 2):
    s.append(str(i))
if n % 2 == 1:
    s += s[::-1][1:]
else:
    s += s[::-1]
s1 = []
for i in range(2, n + 1, 2):
    s1.append(str(i))
if n % 2 == 0:
    s1 += s1[::-1][1:]
else:
    s1 += s1[::-1]
s += s1
s += [str(n)]
print(' '.join(s))

Solution (Python):
from typing import List

def part(n: int, s=1) -> List[int]:
    l = [v for v in range(s, n + 1, 2)]
    if l[-1] == n:
        l = l + list(reversed(l[:-1]))
    else:
        l = l + l[::-1]
    return l

def gen(n: int):
    if n == 1:
        return [1, 1]
    return part(n, 1) + part(n, 2) + [n]
if __name__ == '__main__':
    n = int(input())
    print(' '.join(map(str, gen(n))))

Solution (Python):
def make_seq(n):
    os = list(range(1, n, 2))
    es = list(range(2, n, 2))
    ls = os[:]
    if n % 2 != 0:
        ls += [n]
    ls += os[::-1]
    ls += [n]
    ls += es
    if n % 2 == 0:
        ls += [n]
    ls += es[::-1]
    return ls

def main():
    print(' '.join((str(n) for n in make_seq(int(input())))))
if __name__ == '__main__':
    main()