CF2273F.Pancho's Permutation
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Pancho was given a permutation∗ p1,p2,…,pn as a gift when he was a child. He made many fond memories with his permutation, but the day he turned 18, he realized to his horror that some of the elements of the permutation may have been erased.
Pancho was never great at remembering long sequences of numbers, but he recalls two of its properties:
- For any i (1≤i≤n−1), p1,p2,…,pi was not a permutation of length i.
- For any j (2≤j≤n), pj,pj+1,…,pn was not a permutation of length n−j+1.
Your task is to help Pancho by outputting the k-th smallest permutation in lexicographical order† that matches the information he remembers or reporting that there is no such permutation.
∗A permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).
†An array a is lexicographically smaller than an array b if and only if one of the following holds:
- a is a prefix of b, but a=b; or
- in the first position where a and b differ, the array a has a smaller element than the corresponding element in b.
潘乔小时候收到了一个排列∗ p1,p2,…,pn 作为礼物。他与这个排列一起度过了许多美好时光,但当他年满 18 岁那天,他惊恐地发现该排列中某些元素可能已被擦除。
潘乔向来不擅长记忆长串数字,但他仍记得该排列具备以下两个性质:
- 对任意 i(1≤i≤n−1),前缀 p1,p2,…,pi 不是一个长度为 i 的排列;
- 对任意 j(2≤j≤n),后缀 pj,pj+1,…,pn 不是一个长度为 n−j+1 的排列。
你的任务是帮助潘乔:输出满足他所回忆信息的字典序†第 k 小的排列;若不存在这样的排列,则报告无解。
∗ 长度为 n 的排列是指由 1 到 n 中 n 个互不相同的整数以任意顺序组成的数组。例如,[2,3,1,5,4] 是一个排列,而 [1,2,2] 不是排列(数组中 2 出现了两次),[1,3,4] 也不是排列(此时 n=3,但数组中出现了 4)。
† 数组 a 字典序小于数组 b,当且仅当满足以下条件之一:
- a 是 b 的真前缀(即 a 是 b 的前缀且 a=b);或
- 在 a 与 b 首次出现不同元素的位置上,a 中的对应元素小于 b 中的对应元素。
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤100). The description of the test cases follows.
The first line of each test case contains two integers n and k (2≤n≤106 and 1≤k≤1018) — the length of the permutation and the index of the one you must construct.
The second line of each test case contains n integers p1,p2,…,pn (if pi is known, then 1≤pi≤n; otherwise, pi=−1) — the information provided about the original permutation.
It is guaranteed that the known values pi (those with pi=−1) are pairwise distinct.
It is guaranteed that the sum of n over all test cases does not exceed 106.
每个测试包含多个测试用例。第一行包含测试用例的数量 t(1≤t≤100)。随后是各测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 k(2≤n≤106,1≤k≤1018)—— 分别表示排列的长度以及你需要构造的排列在字典序中的索引(从 1 开始计数)。
每个测试用例的第二行包含 n 个整数 p1,p2,…,pn(若 pi 已知,则 1≤pi≤n;否则 pi=−1)—— 表示关于原始排列的信息。
保证所有已知值 pi(即满足 pi=−1 的那些)两两互异。
保证所有测试用例的 n 值之和不超过 106。
输出格式
Print a line for each test case. Print −1 if there are fewer than k valid permutations. Otherwise, print n integers representing the requested permutation.
为每个测试用例输出一行。如果有效排列的数量少于 k,则输出 −1;否则,输出 n 个整数,表示所要求的排列。
输入输出样例
输入#1
4 5 1 1 2 3 4 5 6 69 -1 -1 -1 -1 -1 -1 4 2 -1 -1 -1 -1 10 10 5 3 9 -1 -1 10 -1 2 -1 -1
输出#1
-1 3 4 1 6 2 5 3 1 4 2 5 3 9 1 6 10 7 2 8 4
说明/提示
In the first test case, the first two elements of the given information are 1 and 2. Since these two numbers are precisely the elements of a permutation of length 2, there are no valid permutations.
In the third test case, there are exactly 2 valid permutations (listed in lexicographical order), [2,4,1,3] and [3,1,4,2].
The answer is the second one, as requested.
在第一个测试用例中,给定信息的前两个元素是 1 和 2。由于这两个数恰好构成一个长度为 2 的排列的全部元素,因此不存在合法的排列。
在第三个测试用例中,恰好存在 2 个合法排列(按字典序列出):[2,4,1,3] 和 [3,1,4,2]。
根据要求,答案为第二个排列。
输入解题思路,AI测评打分。不知道怎么写?