← 返回题目列表

Codeforces · 1945/E

E. 二分查找

中文机器翻译题面 查看原题

安东在徒步旅行中感到无聊,想要解决一些问题。他问基里尔是否有任何新问题,当然,基里尔有一个。

给你一个大小为$$$n$$$的排列$$$p$$$,以及需要找到的数字$$$x$$$。长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 以任意顺序排列。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

您认为自己是一名很酷的程序员,因此您将使用高级算法进行搜索 - 二分搜索。但是,您忘记了对于二分查找,数组必须是排序的。

你并没有放弃,决定应用这个算法,为了得到正确的答案,你可以在运行算法之前执行以下操作不超过$$$2$$$次:选择索引$$$i$$$、$$$j$$$ ($$$1\le i, j \le n$$$)并交换$$$i$$$和$$$j$$$位置的元素。

之后,执行二分查找。在算法开始时,声明了两个变量 $$$l = 1$$$ 和 $$$r = n + 1$$$。然后执行以下循环:

1. 如果$$$r - l = 1$$$,则结束循环
2. $$$m = \lfloor \frac{r + l}{2} \rfloor$$$
3. 如果$$$p_m \le x$$$,则赋值$$$l = m$$$,否则$$$r = m$$$。

目标是在算法之前重新排列排列中的数字,以便在执行算法之后,$$$p_l$$$ 等于$$$x$$$。可以证明 $$$2$$$ 操作总是足够的。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2\cdot 10^4$$$) — 测试用例的数量。然后按照测试用例的描述进行操作。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le x \le n \le 2\cdot 10^5$$$) — 排列的长度和要找到的数字。

第二行包含由空格分隔的排列 $$$p$$$ ($$$1 \le p_i \le n$$$)。

保证所有测试用例的$$$n$$$值的总和不超过$$$2\cdot 10^5$$$。

输出

对于每个测试用例,在第一行输出一个整数 $$$k$$$ ($$$0 \le k \le 2$$$) — 您执行的操作数。在接下来的 $$$k$$$ 行中,输出 $$$2$$$ 整数 $$$i$$$, $$$j$$$ ($$$1 \le i, j \le n$$$),并用空格分隔,表示要交换位置 $$$i$$$ 和 $$$j$$$ 处的元素。

请注意,您不需要最小化操作次数。

示例

输入 #1

5
6 3
1 2 3 4 5 6
6 5
3 1 6 5 2 4
5 1
3 5 4 2 1
6 3
4 3 1 5 2 6
3 2
3 2 1

输出 #1

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