CF1978C.Manhattan Permutations
普及-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
设排列 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 $ ,若存在,输出排列 $ p $ 。
输入格式
每个测试点包含多组数据。
第一行包括一个整数 $ t $ ( $ 1 \leq t \leq 10^{4} $ ),表示测试数据的组数。
接下来 $ t $ 行,每行包括两个整数 $ 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"和"No"大小写不敏感(例如,"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
输入解题思路,AI测评打分。不知道怎么写?