CF2273F Pancho's Permutation

Pancho 小时候收到了一份礼物，是一个排列 $p_1, p_2, \ldots, p_n$。他与这个排列共同度过了美好的时光，但在他 18 岁生日时，惊恐地发现排列中的部分元素可能被抹去了。 Pancho 一直不擅长记长数字序列，但他记得这个排列有以下两个性质： - 对任意 $i$（$1 \le i \le n-1$），$p_1, p_2, \ldots, p_i$ 不是长度为 $i$ 的一个排列。 - 对任意 $j$（$2 \le j \le n$），$p_j, p_{j+1}, \ldots, p_n$ 不是长度为 $n-j+1$ 的一个排列。 你的任务是帮 Pancho 输出按字典序排序后的第 $k$ 小个满足上述条件的排列，或者报告不存在这样的排列。 一个长度为 $n$ 的排列是由 $1$ 到 $n$ 的不同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ （$2$ 出现两次）和 $[1,3,4]$（长度为 $3$，但包含 $4$）都不是排列。 数组 $a$ 在字典序上小于数组 $b$，当且仅当以下两种情况之一成立： - $a$ 是 $b$ 的前缀，且 $a \neq b$； - 在第一个不同的位置，$a$ 的元素小于 $b$ 上的对应元素。

每个测试包含多个测试用例。第一行包含测试用例数 $t$（$1 \leq t \leq 100$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 10^6$，$1 \leq k \leq 10^{18}$），表示排列的长度和你需要构造的第 $k$ 个答案的字典序编号。 第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（若 $p_i$ 已知，则 $1 \leq p_i \leq n$；否则 $p_i = -1$），即关于原排列的已知信息。 保证所有已知的 $p_i$（即 $p_i \neq -1$）两两不同。 保证所有测试用例中 $n$ 的总和不超过 $10^6$。

每个测试用例输出一行。如果满足条件的排列数小于 $k$，输出 $-1$；否则输出 $n$ 个整数，即所要求的排列。

第一个样例中，前两个已知元素为 $1,2$。由于这两个数正好组成一个长度为 $2$ 的排列，因此没有满足条件的排列。 第三个样例中，恰好有 $2$ 个有效排列（按字典序排序分别为 $[2, 4, 1, 3]$ 和 $[3, 1, 4, 2]$）。 答案即为要求的第二个排列。 由 ChatGPT 5 翻译