P15075 [ICPC 2024 Chengdu R] Closest Derangement

Blackbird 有一个长度为 $n$ 的排列 $p$，他想找到 $p$ 的一个错位排列 $q$，即 $q$ 是另一个长度为 $n$ 的排列，且对于 $i=1,2,\ldots,n$，都有 $q_i\neq p_i$。与此同时，他希望 $\sum_{i=1}^{n}|p_i-q_i|$ 取到最小值。满足上述条件的排列 $q$，称为 $p$ 的最近错位排列。 $p$ 的最近错位排列可能有多个，你需要输出字典序第 $k$ 小的最近错位排列。如果 $p$ 的最近错位排列少于 $k$ 个，则输出 $-1$。 一个长度为 $n$ 的排列，是指一个长度为 $n$ 的序列，满足所有元素互不相同且均为从 $1$ 到 $n$ 的正整数。排列可以按字典序排序。设 $a$ 和 $b$ 是两个长度为 $n$ 的不同的排列。那么，$a < b$ 当且仅当对于满足 $a_i \neq b_i$ 的最小下标 $i$，有 $a_i < b_i$。

第一行包含一个整数 $T$（$1\le T\le 10^4$），表示测试数据组数。 对于每组数据，第一行包含两个正整数 $n$（$2\le n \le 2 \cdot 10^5$）和 $k$（$1\le k \le 10^9$）。第二行包含 $n$ 个正整数 $p_1, p_2, \ldots, p_n$ 。保证 $p$ 是一个排列。 保证每组数据中 $n$ 之和不超过 $10^6$。

对于每组数据，如果最近错位排列的数量不少于 $k$，则输出 $n$ 个正整数 $q_1, q_2, \ldots, q_n$ ，表示 $p$ 的字典序第 $k$ 小的最近错位排列。否则输出 $-1$。

第一个测试用例中，$[1,2]$ 是唯一的最近错位排列，所以输出 $-1$。 第二个测试用例中，$[2,3,1]$ 和 $[3,1,2]$ 是 $p$ 的最近错位排列，且 $[3,1,2]$ 的字典序大于 $[2,3,1]$。