#CF2272A. Maximize One MEX

Maximize One MEX

题目描述

给定一个长度为 nn 的数组 aa,它是整数 0,1,…,n−10,1,\ldots,n-1 的一个排列。你可以执行以下操作至多一次:

  • 选择两个不同的下标 ii 和 jj(i≠ji \ne j),交换 aia_i 和 aja_j 的值。

执行操作后,定义 fi=mex⁡(a1,a2,…,ai)f_i=\operatorname{mex}(a_1, a_2, \ldots, a_i)。mex⁡(c)\operatorname{mex}(c) 表示集合 cc 的最小排除值(MEX)∗^{\text{∗}}。

给定一个整数 kk,找到在上述操作中使用的两个下标,使得 f1,f2,…,fnf_1, f_2, \ldots, f_n 中第 kk 大的值最大化。如果不需要操作,输出 −1-1。

如果有多个合法答案,输出任意一个均可。

∗^{\text{∗}}整数集合 c1,c2,…,ckc_1, c_2, \ldots, c_k 的最小排除值(MEX)定义为不在集合 cc 中出现的最小非负整数 xx。

输入格式

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

对于每个测试用例,第一行包含两个整数 nn 和 kk(2≤n≤1002 \le n \le 100,1≤k≤n1 \le k \le n),其中 nn 是数组 aa 的元素个数,kk 是要最大化的值的排名(k=1k=1 对应最大值)。

下一行包含 nn 个整数:a1,a2,…,ana_1,a_2,\ldots,a_n。保证 0,1,…,n−10,1,\ldots,n−1 中的每个值在数组 aa 中恰好出现一次。

保证所有测试用例的 nn 之和不超过 100100。

输出格式

对于每个测试用例,输出一行,包含在操作中使用的两个下标,以使 f1,f2,…,fnf_1, f_2, \ldots, f_n 中第 kk 大的值最大化。如果不需要操作,输出 −1-1。

样例

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

说明

在第一个测试用例中,不需要任何操作;f1,f2,…,f5f_1, f_2, \ldots, f_5 中第 11 大的值是 f5=5f_5=5。实际上,如果执行交换操作,无论选择哪两个下标,f5f_5 始终是最大的,值为 55。

在第二个测试用例中,交换 a1a_1 和 a3a_3 后,得到数组 [1,0,2][1,0,2],且 f1=0,f2=2,f3=3f_1=0, f_2=2, f_3=3;f1,f2,f3f_1, f_2, f_3 中第 22 大的值是 f2=2f_2=2。

来源

导入自 Codeforces — Codeforces Round 1130 (Div. 2).