CF2273F.Pancho's Permutation

NOI/NOI+/CTSC

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

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

题目描述

Pancho was given a permutation∗^{\text{∗}} p1,p2,…,pnp_1, p_2, \ldots, p_n as a gift when he was a child. He made many fond memories with his permutation, but the day he turned 1818, 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 ii (1≤i≤n−11 \le i \le n-1), p1,p2,…,pip_1, p_2, \ldots, p_i was not a permutation of length ii.
  • For any jj (2≤j≤n2 \le j \le n), pj,pj+1,…,pnp_j, p_{j+1}, \ldots, p_n was not a permutation of length n−j+1n-j+1.

Your task is to help Pancho by outputting the kk-th smallest permutation in lexicographical order†^{\text{†}} that matches the information he remembers or reporting that there is no such permutation.

∗^{\text{∗}}A permutation of length nn is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (n=3n=3 but there is 44 in the array).

†^{\text{†}}An array aa is lexicographically smaller than an array bb if and only if one of the following holds:

  • aa is a prefix of bb, but a≠ba \neq b; or
  • in the first position where aa and bb differ, the array aa has a smaller element than the corresponding element in bb.

潘乔小时候收到了一个排列∗^{\text{∗}} p1,p2,…,pnp_1, p_2, \ldots, p_n 作为礼物。他与这个排列一起度过了许多美好时光,但当他年满 18 岁那天,他惊恐地发现该排列中某些元素可能已被擦除。

潘乔向来不擅长记忆长串数字,但他仍记得该排列具备以下两个性质:

  • 对任意 ii(1≤i≤n−11 \le i \le n-1),前缀 p1,p2,…,pip_1, p_2, \ldots, p_i 不是一个长度为 ii 的排列;
  • 对任意 jj(2≤j≤n2 \le j \le n),后缀 pj,pj+1,…,pnp_j, p_{j+1}, \ldots, p_n 不是一个长度为 n−j+1n-j+1 的排列。

你的任务是帮助潘乔:输出满足他所回忆信息的字典序†^{\text{†}}第 kk 小的排列;若不存在这样的排列,则报告无解。

∗^{\text{∗}} 长度为 nn 的排列是指由 11 到 nn 中 nn 个互不相同的整数以任意顺序组成的数组。例如,[2,3,1,5,4][2,3,1,5,4] 是一个排列,而 [1,2,2][1,2,2] 不是排列(数组中 22 出现了两次),[1,3,4][1,3,4] 也不是排列(此时 n=3n=3,但数组中出现了 44)。

†^{\text{†}} 数组 aa 字典序小于数组 bb,当且仅当满足以下条件之一:

  • aa 是 bb 的真前缀(即 aa 是 bb 的前缀且 a≠ba \neq b);或
  • 在 aa 与 bb 首次出现不同元素的位置上,aa 中的对应元素小于 bb 中的对应元素。

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1001 \leq t \leq 100). The description of the test cases follows.

The first line of each test case contains two integers nn and kk (2≤n≤1062 \leq n \leq 10^6 and 1≤k≤10181 \leq k \leq 10^{18}) — the length of the permutation and the index of the one you must construct.

The second line of each test case contains nn integers p1,p2,…,pnp_1,p_2,\dots,p_n (if pip_i is known, then 1≤pi≤n1 \leq p_i \leq n; otherwise, pi=−1p_i=-1) — the information provided about the original permutation.

It is guaranteed that the known values pip_i (those with pi≠−1p_i \neq -1) are pairwise distinct.

It is guaranteed that the sum of nn over all test cases does not exceed 10610^6.

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1001 \leq t \leq 100)。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 nn 和 kk(2≤n≤1062 \leq n \leq 10^6,1≤k≤10181 \leq k \leq 10^{18})—— 分别表示排列的长度以及你需要构造的排列在字典序中的索引(从 1 开始计数)。

每个测试用例的第二行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\dots,p_n(若 pip_i 已知,则 1≤pi≤n1 \leq p_i \leq n;否则 pi=−1p_i = -1)—— 表示关于原始排列的信息。

保证所有已知值 pip_i(即满足 pi≠−1p_i \neq -1 的那些)两两互异。

保证所有测试用例的 nn 值之和不超过 10610^6。

输出格式

Print a line for each test case. Print −1-1 if there are fewer than kk valid permutations. Otherwise, print nn integers representing the requested permutation.

为每个测试用例输出一行。如果有效排列的数量少于 kk,则输出 −1-1;否则,输出 nn 个整数,表示所要求的排列。

输入输出样例

  • 输入#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 11 and 22. Since these two numbers are precisely the elements of a permutation of length 22, there are no valid permutations.

In the third test case, there are exactly 22 valid permutations (listed in lexicographical order), [2,4,1,3][2, 4, 1, 3] and [3,1,4,2][3, 1, 4, 2].

The answer is the second one, as requested.

在第一个测试用例中,给定信息的前两个元素是 11 和 22。由于这两个数恰好构成一个长度为 22 的排列的全部元素,因此不存在合法的排列。

在第三个测试用例中,恰好存在 22 个合法排列(按字典序列出):[2,4,1,3][2, 4, 1, 3] 和 [3,1,4,2][3, 1, 4, 2]。

根据要求,答案为第二个排列。

输入解题思路,AI测评打分。不知道怎么写?

首页