Special Permutation (Codeforces 1612B)
Tags: Greedy, constructive algorithms

A permutation of length $$$n$$$ is an array $$$p=[p_1,p_2,\dots, p_n]$$$ which contains every integer from $$$1$$$ to $$$n$$$ (inclusive) exactly once. For example, $$$p=[4, 2, 6, 5, 3, 1]$$$ is a permutation of length $$$6$$$.You are given three integers $$$n$$$, $$$a$$$ and $$$b$$$, where $$$n$$$ is an even number. Print any permutation of length $$$n$$$ that the minimum among all its elements of the left half equals $$$a$$$ and the maximum among all its elements of the right half equals $$$b$$$. Print -1 if no such permutation exists.

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$), the number of test cases in the test. The following $$$t$$$ lines contain test case descriptions.Each test case description contains three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$2 \le n \le 100$$$; $$$1 \le a,b \le n$$$; $$$a \ne b$$$), where $$$n$$$ is an even number (i.e. $$$n \bmod 2 = 0$$$).

Output: For each test case, print a single line containing any suitable permutation. Print -1 no such permutation exists. If there are multiple answers, print any of them.


Sample Inputs:
7
6 2 5
6 1 3
6 4 3
4 2 4
10 5 3
2 1 2
2 2 1

Sample Outputs:
4 2 6 5 3 1
-1
6 4 5 1 3 2 
3 2 4 1 
-1
1 2 
2 1

Solution (Python):
def solve(n, a, b):
    left = [a]
    right = [b]
    extra = []
    for i in range(n, 0, -1):
        if i == a or i == b:
            continue
        if a < i < b:
            extra.append(i)
        elif i > a:
            left.append(i)
        elif i < b:
            right.append(i)
    while extra and len(left) < n // 2:
        left.append(extra.pop())
    while extra and len(right) < n // 2:
        right.append(extra.pop())
    if len(right) == len(left) == n // 2:
        return ' '.join(map(str, left)) + ' ' + ' '.join(map(str, right))
    else:
        return -1

def print_solution(solution):
    print(solution)

def main():
    t = int(input().strip())
    for _ in range(t):
        (n, a, b) = list(map(int, input().strip().split()))
        solution = solve(n, a, b)
        print_solution(solution)
if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    (n, a, b) = map(int, input().split())
    ans = []
    for i in range(n, 0, -1):
        if i not in (a, b):
            ans.append(i)
    ans = [a] + ans + [b]
    if min(ans[:n // 2]) == a and max(ans[n // 2:]) == b:
        print(' '.join(map(str, ans)))
    else:
        print(-1)
for i in range(int(input())):
    solve()

Solution (Python):
from collections import *
from functools import *
import sys
input = lambda : sys.stdin.readline().rstrip()
Z = int(input())
for _ in range(Z):
    (n, l, r) = map(int, input().split())
    dp = list(range(1, n + 1))[::-1]
    dp.pop(dp.index(l))
    dp.pop(dp.index(r))
    dp.insert(0, l)
    dp.append(r)
    if l == min(dp[:n // 2]) and r == max(dp[n // 2:]):
        print(' '.join(map(str, dp)))
    else:
        print(-1)