codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1608B.md (1627B)


      1 Source: https://codeforces.com/problemset/problem/1608/B
      2 
      3 B. Build the Permutation
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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:
     22 
     23 * There are exactly $a$ integers $i$ with $2 \le i \le n-1$ such that $p_{i-1} \lt p_i \gt p_{i+1}$ (in other words, there are exactly $a$ local maximums).
     24 * There are exactly $b$ integers $i$ with $2 \le i \le n-1$ such that $p_{i-1} \gt p_i \lt p_{i+1}$ (in other words, there are exactly $b$ local minimums).
     25 
     26 If such permutations exist, find any such permutation.
     27 
     28 Input
     29 
     30 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.
     31 
     32 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$).
     33 
     34 The sum of $n$ over all test cases doesn't exceed $10^5$.
     35 
     36 Output
     37 
     38 For each test case, if there is no permutation with the requested properties, output $-1$.
     39 
     40 Otherwise, print the permutation that you are found. If there are several such permutations, you may print any of them.
     41 
     42 Example
     43 
     44 Input
     45 
     46 ```
     47 3
     48 4 1 1
     49 6 1 2
     50 6 4 0
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 1 3 2 4
     57 4 2 3 1 5 6
     58 -1
     59 ```
     60 
     61 Note
     62 
     63 In the first test case, one example of such permutations is $[1, 3, 2, 4]$. In it $p_1 \lt p_2 \gt p_3$, and $2$ is the only such index, and $p_2 \gt p_3 \lt p_4$, and $3$ the only such index.
     64 
     65 One can show that there is no such permutation for the third test case.