311180: CF1945E. Binary Search
Description
Anton got bored during the hike and wanted to solve something. He asked Kirill if he had any new problems, and of course, Kirill had one.
You are given a permutation $p$ of size $n$, and a number $x$ that needs to be found. 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).
You decided that you are a cool programmer, so you will use an advanced algorithm for the search — binary search. However, you forgot that for binary search, the array must be sorted.
You did not give up and decided to apply this algorithm anyway, and in order to get the correct answer, you can perform the following operation no more than $2$ times before running the algorithm: choose the indices $i$, $j$ ($1\le i, j \le n$) and swap the elements at positions $i$ and $j$.
After that, the binary search is performed. At the beginning of the algorithm, two variables $l = 1$ and $r = n + 1$ are declared. Then the following loop is executed:
- If $r - l = 1$, end the loop
- $m = \lfloor \frac{r + l}{2} \rfloor$
- If $p_m \le x$, assign $l = m$, otherwise $r = m$.
The goal is to rearrange the numbers in the permutation before the algorithm so that after the algorithm is executed, $p_l$ is equal to $x$. It can be shown that $2$ operations are always sufficient.
InputEach test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 2\cdot 10^4$) — the number of test cases. Then follow the descriptions of the test cases.
The first line of each test case contains two integers $n$ and $x$ ($1 \le x \le n \le 2\cdot 10^5$) — the length of the permutation and the number to be found.
The second line contains the permutation $p$ separated by spaces ($1 \le p_i \le n$).
It is guaranteed that the sum of the values of $n$ for all test cases does not exceed $2\cdot 10^5$.
OutputFor each test case, output an integer $k$ ($0 \le k \le 2$) on the first line — the number of operations performed by you. In the next $k$ lines, output $2$ integers $i$, $j$ ($1 \le i, j \le n$) separated by a space, indicating that you are swapping the elements at positions $i$ and $j$.
Note that you do not need to minimize the number of operations.
ExampleInput5 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 1Output
0 1 3 4 2 2 4 1 5 2 4 5 2 4 1 1 3
Output
这个题目是关于二分查找的。给定一个长度为n的排列p和一个需要查找的数字x。排列是1到n的n个不同的整数的任意顺序数组。在执行二分查找之前，你可以执行不超过2次以下操作：选择索引i,j(1≤i,j≤n)并交换位置i和j的元素。然后执行二分查找算法。算法的目标是通过重新排列排列中的数字，使得算法执行后，p_l等于x。可以证明，2次操作总是足够的。
输入数据格式：
第一行包含一个整数t(1≤t≤2∗10^4)——测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含两个整数n和x(1≤x≤n≤2∗10^5)——排列的长度和需要找到的数字。
第二行包含由空格分隔的排列p(1≤p_i≤n)。
输出数据格式：
对于每个测试用例，第一行输出一个整数k(0≤k≤2)——你执行的操作次数。在接下来的k行中，输出两个由空格分隔的整数i,j(1≤i,j≤n)，表示你正在交换位置i和j的元素。题目大意： 这个题目是关于二分查找的。给定一个长度为n的排列p和一个需要查找的数字x。排列是1到n的n个不同的整数的任意顺序数组。在执行二分查找之前，你可以执行不超过2次以下操作：选择索引i,j(1≤i,j≤n)并交换位置i和j的元素。然后执行二分查找算法。算法的目标是通过重新排列排列中的数字，使得算法执行后，p_l等于x。可以证明，2次操作总是足够的。 输入数据格式： 第一行包含一个整数t(1≤t≤2∗10^4)——测试用例的数量。然后是测试用例的描述。 每个测试用例的第一行包含两个整数n和x(1≤x≤n≤2∗10^5)——排列的长度和需要找到的数字。 第二行包含由空格分隔的排列p(1≤p_i≤n)。 输出数据格式： 对于每个测试用例，第一行输出一个整数k(0≤k≤2)——你执行的操作次数。在接下来的k行中，输出两个由空格分隔的整数i,j(1≤i,j≤n)，表示你正在交换位置i和j的元素。