CF1978C.Manhattan Permutations

普及-

通过率:0%

AC君温馨提醒

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

题目描述

设排列 pp 的曼哈顿值为 $ |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测评打分。不知道怎么写?

首页