CF1608B.Build the Permutation

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given three integers n,a,bn, a, b. Determine if there exists a permutation p1,p2,…,pnp_1, p_2, \ldots, p_n of integers from 11 to nn, such that:

  • There are exactly aa integers ii with 2≤i≤n−12 \le i \le n-1 such that pi−1<pi>pi+1p_{i-1} \lt p_i \gt p_{i+1} (in other words, there are exactly aa local maximums).

  • There are exactly bb integers ii with 2≤i≤n−12 \le i \le n-1 such that pi−1>pi<pi+1p_{i-1} \gt p_i \lt p_{i+1} (in other words, there are exactly bb local minimums).

If such permutations exist, find any such permutation.

给你三个整数 n,a,bn, a, b。判断是否存在一个由 11 到 nn 的整数组成的排列 p1,p2,…,pnp_1, p_2, \ldots, p_n,使得:

  • 恰好有 aa 个下标 ii(满足 2≤i≤n−12 \le i \le n-1),使得 pi−1<pi>pi+1p_{i-1} \lt p_i \gt p_{i+1}(即恰好有 aa 个局部最大值);

  • 恰好有 bb 个下标 ii(满足 2≤i≤n−12 \le i \le n-1),使得 pi−1>pi<pi+1p_{i-1} \gt p_i \lt p_{i+1}(即恰好有 bb 个局部最小值)。

如果这样的排列存在,请构造出任意一个满足条件的排列。

输入格式

The first line of the input contains a single integer tt (1≤t≤1041 \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 nn, aa and bb (2≤n≤1052 \leq n \leq 10^5, 0≤a,b≤n0 \leq a,b \leq n).

The sum of nn over all test cases doesn't exceed 10510^5.

输入的第一行包含一个整数 tt(1≤t≤1041 \le t \le 10^4),表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅一行,包含三个整数 nn、aa 和 bb(2≤n≤1052 \leq n \leq 10^5,0≤a,b≤n0 \leq a,b \leq n)。

所有测试用例的 nn 值之和不超过 10510^5。

输出格式

For each test case, if there is no permutation with the requested properties, output −1-1.

Otherwise, print the permutation that you are found. If there are several such permutations, you may print any of them.

对于每个测试用例,若不存在满足要求的排列,则输出 −1-1。

否则,输出你找到的排列。若存在多个满足条件的排列,你可以输出其中任意一个。

输入输出样例

  • 输入#1

    3
    4 1 1
    6 1 2
    6 4 0

    输出#1

    1 3 2 4
    4 2 3 1 5 6
    -1

说明/提示

In the first test case, one example of such permutations is [1,3,2,4][1, 3, 2, 4]. In it p1<p2>p3p_1 \lt p_2 \gt p_3, and 22 is the only such index, and p2>p3<p4p_2 \gt p_3 \lt p_4, and 33 the only such index.

One can show that there is no such permutation for the third test case.

在第一个测试用例中,一个满足条件的排列示例是 [1,3,2,4][1, 3, 2, 4]。其中 p1<p2>p3p_1 \lt p_2 \gt p_3,而 22 是唯一满足该不等式模式的下标;同时 p2>p3<p4p_2 \gt p_3 \lt p_4,而 33 是唯一满足该不等式模式的下标。

可以证明,第三个测试用例不存在满足条件的排列。

输入解题思路,AI测评打分。不知道怎么写?

首页