#P16897. [Ontak2026]非常饥饿的蜥蜴

[Ontak2026]非常饥饿的蜥蜴

[ONTAK 2026] 非常饥饿的蜥蜴

题目描述

Bytek 收藏了许多非常饥饿的蜥蜴。他有 nn 只蜥蜴,它们的大小恰好分别为 1,2,…,n1,2,\ldots,n。Bytek 可以把这些蜥蜴按任意顺序排成一行放入展示缸中。

放入展示缸后,每一秒都会发生如下过程:

  • 所有蜥蜴同时行动;
  • 如果一只蜥蜴左边紧邻着一只比它更小的蜥蜴,那么它会吃掉这只左邻居;
  • 本秒所有捕食行为结束后,被吃掉的蜥蜴消失,其余蜥蜴重新紧密排列;
  • 如果某一秒开始时已经没有任何蜥蜴能够吃掉自己的左邻居,则整个过程结束。

注意,一只蜥蜴可以在同一秒中既吃掉左边的蜥蜴,又被右边的蜥蜴吃掉。

例如,若初始排列为

(1,3,2,4,5),

则:

  • 第 11 秒中,蜥蜴 33 吃掉 11,蜥蜴 44 吃掉 22,同时蜥蜴 55 吃掉 44。这一秒结束后排列变为 (3,5);
  • 第 22 秒中,蜥蜴 55 吃掉 33,排列变为 (5);
  • 此时过程结束。

Bytek 还给出了一个长度为 nn 的序列

(a1,a2,…,an)(a_1,a_2,\ldots,a_n)。

这里的下标 ii 表示的是初始排列中的位置,而不是蜥蜴的大小。

具体来说:

  • 若 ai>0a_i>0,则要求初始时位于第 ii 个位置的蜥蜴恰好在第 aia_i 秒被吃掉;
  • 若 ai=−1a_i=-1,则要求初始时位于第 ii 个位置的蜥蜴一直存活到整个过程结束。

如果一个初始排列满足上述所有要求,就称它为一个美观排列。


接下来定义美观排列之间的大小关系。

对于一个排列 p=(p1,p2,…,pn)p=(p_1,p_2,\ldots,p_n),记 pos⁡p(x)\operatorname{pos}_p(x) 表示大小为 xx 的蜥蜴在排列 pp 中的位置。

比较两个排列 pp 和 qq 时,按照下面两个序列的字典序进行比较:

$(\operatorname{pos}_p(1),\operatorname{pos}_p(2),\ldots,\operatorname{pos}_p(n))$

和

$(\operatorname{pos}_q(1),\operatorname{pos}_q(2),\ldots,\operatorname{pos}_q(n))$。

也就是说,找到最小的大小 xx,使得大小小于 xx 的所有蜥蜴在两个排列中的位置都相同。如果

pos⁡p(x)<pos⁡q(x)\operatorname{pos}_p(x)<\operatorname{pos}_q(x),

那么认为 p<qp<q。

你的任务是求按照上述顺序排列后的第 kk 个美观排列。

输入格式

第一行包含两个整数 n,kn,k。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

数据保证:

  • 1≤n≤1051\le n\le 10^5;
  • 1≤k≤101\le k\le 10;
  • −1≤ai≤n-1\le a_i\le n;
  • ai≠0a_i\ne0。

输出格式

如果至少存在 kk 个美观排列,输出一行 nn 个整数

b1,b2,…,bnb_1,b_2,\ldots,b_n,

其中 bib_i 表示第 kk 小的美观排列中,初始时位于第 ii 个位置的蜥蜴大小。

如果不存在第 kk 个美观排列,输出:

-1

样例 1

5 1
1 2 1 -1 -1
1 3 2 5 4

样例 1 说明

初始排列为

(1,3,2,5,4)。

第 11 秒:

  • 蜥蜴 33 吃掉 11;
  • 蜥蜴 55 吃掉 22。

排列变为

(3,5,4)。

第 22 秒:

  • 蜥蜴 55 吃掉 33。

排列变为

(5,4),

之后不再有蜥蜴能够吃掉左邻居,过程结束。

因此,按照初始位置来看:

初始位置 蜥蜴大小 被吃时间
1
2 3 2
3 2 1
4 5 −1-1
5 4

恰好得到序列

1 2 1 -1 -1。

样例 2

5 10
1 2 1 -1 -1
-1

子任务

子任务 限制 分值
1 n≤9n\le9 7
2 n≤2000n\le2000 25
3 k=1k=1 31
4 k≤2k\le2 18
5 无额外限制 19