← 返回题目列表

Codeforces · 1978/C

C. 曼哈顿排列

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

我们将排列的曼哈顿值称为 $$$^{\dagger}$$$ $$$p$$$ 表达式 $$$|p_1 - 1| 的值+ |p_2 - 2| + \ldots + |p_n - n|$$$。

例如,对于排列 $$$[1, 2, 3]$$$,曼哈顿值为 $$$|1 - 1| + |2 - 2| + |3 - 3| = 0$$$,对于排列 $$$[3, 1, 2]$$$,曼哈顿值为 $$$|3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4$$$。

给定整数 $$$n$$$ 和 $$$k$$$。找到长度为 $$$n$$$ 的排列 $$$p$$$,使其曼哈顿值等于 $$$k$$$,或者确定不存在这样的排列。

$$$^{\dagger}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^{5}, 0 \le k \le 10^{12}$$$) — 排列的长度和所需的曼哈顿值。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,如果没有合适的排列,则输出“No”。否则,在第一行中输出“Yes”,在第二行中输出 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — 一个合适的排列。

如果有多个解,则输出其中任意一个。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

8
3 4
4 5
7 0
1 1000000000000
8 14
112 777
5 12
5 2

输出 #1

Yes
3 1 2
No
Yes
1 2 3 4 5 6 7
No
Yes
8 2 3 4 5 6 1 7
No
Yes
5 4 3 1 2
Yes
2 1 3 4 5

注意

在第一个测试用例中,排列 $$$[3, 1, 2]$$$ 是合适的,它的曼哈顿值为 $$$|3 - 1| + |1 - 2| + |2 - 3| = 2 + 1 + 1 = 4$$$。

在第二个测试用例中,可以证明不存在长度为 $$$4$$$ 且曼哈顿值为 $$$5$$$ 的排列。

在第三个测试用例中,排列 $$$[1,2,3,4,5,6,7]$$$ 是合适的,其曼哈顿值是 $$$|1-1|+|2-2|+|3-3|+|4-4|+|5-5|+|6-6|+|7-7|=0$$$。