Build the Permutation (Codeforces 1608B)
Tags: Greedy, constructive algorithms

You are given three integers $$$n, a, b$$$. Determine if there exists a permutation $$$p_1, p_2, \ldots, p_n$$$ of integers from $$$1$$$ to $$$n$$$, such that:There are exactly $$$a$$$ integers $$$i$$$ with $$$2 \le i \le n-1$$$ such that $$$p_{i-1} < p_i > p_{i+1}$$$ (in other words, there are exactly $$$a$$$ local maximums).There are exactly $$$b$$$ integers $$$i$$$ with $$$2 \le i \le n-1$$$ such that $$$p_{i-1} > p_i < p_{i+1}$$$ (in other words, there are exactly $$$b$$$ local minimums).If such permutations exist, find any such permutation.

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of test cases follows.The only line of each test case contains three integers $$$n$$$, $$$a$$$ and $$$b$$$ ($$$2 \leq n \leq 10^5$$$, $$$0 \leq a,b \leq n$$$).The sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output: For each test case, if there is no permutation with the requested properties, output $$$-1$$$.Otherwise, print the permutation that you are found. If there are several such permutations, you may print any of them.

Note: In the first test case, one example of such permutations is $$$[1, 3, 2, 4]$$$. In it $$$p_1 < p_2 > p_3$$$, and $$$2$$$ is the only such index, and $$$p_2> p_3 < p_4$$$, and $$$3$$$ the only such index.One can show that there is no such permutation for the third test case.

Sample Inputs:
3
4 1 1
6 1 2
6 4 0

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

Solution (Python):
def max_amount_of_local(n):
    if n == 2:
        return 0
    if n == 3:
        return 1
    if n == 4:
        return 1
    if n == 5:
        return 2
    return (n - 1) // 2

def score(res):
    min_amount = 0
    max_amount = 0
    for i in range(1, len(res) - 1):
        if res[i] > max(res[i - 1], res[i + 1]):
            max_amount += 1
        if res[i] < min(res[i - 1], res[i + 1]):
            min_amount += 1
    return (max_amount, min_amount)

def solve(n, a, b):
    if max_amount_of_local(n) < max(a, b):
        return -1
    if a + b > n - 2:
        return -1
    if abs(a - b) > 1:
        return -1
    if a < b:
        return [n + 1 - val for val in solve(n, b, a)]
    res = [1]
    cur_max = n
    cur_min = 2
    while b > 0:
        res.append(cur_max)
        res.append(cur_min)
        cur_max -= 1
        cur_min += 1
        a -= 1
        b -= 1
    if a == 0:
        for i in range(cur_min, cur_max + 1):
            res.append(i)
        return res
    res.append(cur_max)
    cur_max -= 1
    for i in range(cur_max, cur_min - 1, -1):
        res.append(i)
    return res
T = int(input())
for _ in range(T):
    (n, a, b) = map(int, input().split())
    result = solve(n, a, b)
    if result == -1:
        print(result)
    else:
        print(' '.join(map(str, result)))

Solution (Python):
""""""
from typing import List
import collections, bisect, heapq, itertools, functools, math

class Solution:

    def solve(self, n, a, b):
        diff = a - b
        if abs(diff) > 1 or a + b + 2 > n:
            return [-1]
        if a == b == 0:
            return list(range(1, n + 1))
        sol = [0] * n
        if diff == 1:
            x = a + b + 2
            largest_x_nums = range(n - x + 1, n + 1)
            for i in range(len(largest_x_nums) // 2):
                sol[i * 2] = largest_x_nums[i]
                sol[i * 2 + 1] = largest_x_nums[~i]
            i += 1
            sol[i * 2] = largest_x_nums[i]
            sol[i * 2 + 1:] = list(range(n - x, 0, -1))
        elif diff == -1:
            x = a + b + 2
            smallest_x_nums = range(1, x + 1)
            for i in range(len(smallest_x_nums) // 2):
                sol[i * 2] = smallest_x_nums[~i]
                sol[i * 2 + 1] = smallest_x_nums[i]
            i += 1
            sol[i * 2] = smallest_x_nums[i]
            sol[i * 2 + 1:] = list(range(x + 1, n + 1))
        else:
            x = a + b + 2
            largest_x_nums = range(n - x + 1, n + 1)
            for i in range(len(largest_x_nums) // 2):
                sol[i * 2] = largest_x_nums[~i]
                sol[i * 2 + 1] = largest_x_nums[i]
            i += 1
            sol[i * 2:] = list(range(n - x, 0, -1))
        return sol
if __name__ == '__main__':
    for _ in range(int(input())):
        args = list(map(int, input().split()))
        sol = Solution().solve(*args)
        print(' '.join(map(str, sol)))

Solution (Python):
i = int(input())

def f(n, a, b):
    if abs(a - b) > 1 or a + b > n - 2:
        return [-1]
    perm = []
    if a >= b:
        for i in range(1, n - a - b):
            perm.append(i)
        lower = n - a - b
        upper = n
        while lower < upper:
            perm.append(upper)
            perm.append(lower)
            upper -= 1
            lower += 1
        if lower == upper:
            perm.append(lower)
    else:
        for i in range(n - a - b, 0, -1):
            perm.append(i)
        lower = n - a - b + 1
        upper = n
        while lower < upper:
            perm.append(upper)
            perm.append(lower)
            upper -= 1
            lower += 1
        if lower == upper:
            perm.append(lower)
    return perm
for w in range(0, i):
    [n, a, b] = [int(x) for x in input().split()]
    print(' '.join([str(x) for x in f(n, a, b)]))