← 返回题目列表

AtCoder · arc206_d

D. 最长递增子序列与最长递减子序列的交集

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

排列的元素之一 P=(P_1,\ldots,P_N) of (1,\ldots,N),满足以下条件的元素称为好元素:

  • 该元素可以包含在最长递增子序列和最长递减子序列中 P.

给你整数 N 和 K。判断是否存在排列 P of (1,\ldots,N) 这样正好有 K 好元素,如果存在,就找一个。

回答 T 测试用例。

约束

  • 所有输入值均为整数
  • 1 \leq T \leq 2\times 10^5
  • 1 \leq N \leq 2\times 10^5
  • 0\leq K \leq N
  • 总和 N 所有测试用例不超过 2\times 10^5.

输入

输入由标准输入按以下格式给出:

T
\mathrm{case}_1
\vdots
\mathrm{case}_T

每个测试用例均按以下格式给出:

N K

输出

输出 T 行。

对于 i-第行,如果不存在满足条件的排列 i- 第一个测试用例,输出 -1。 如果存在,则按以下格式输出其中之一:

P_1 \ldots P_N

如果有多个满足条件的解,则接受其中任何一个。


示例输入 1

3
1 0
7 2
2 1

示例输出 1

-1
7 4 6 2 3 1 5
-1

在 2-nd 测试用例, P_4=2 和 P_5=3 是很好的元素。

确实, (2,3,5) 是最长递增子序列 P。另外, (7,6,2,1) 和 (7, 6, 3, 1) 是最长的递减子序列 P.

因此,在此示例输出中, 2 和 3 是很好的元素。其他元素都不是好元素,因此该输出满足条件。

在 1-st 和 3-rd 测试用例,不存在满足条件的排列。因此,输出 -1.