2121D.md (3012B)
1 Source: https://codeforces.com/problemset/problem/2121/D 2 3 D. 1709 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two arrays of integers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$. It is guaranteed that each integer from $1$ to $2 \cdot n$ appears in exactly one of the arrays. 22 23 You need to perform a certain number of operations (possibly zero) so that both of the following conditions are satisfied: 24 25 * For each $1 \leq i \lt n$, it holds that $a_i \lt a_{i + 1}$ and $b_i \lt b_{i + 1}$. 26 * For each $1 \leq i \leq n$, it holds that $a_i \lt b_i$. 27 28 During each operation, you can perform exactly one of the following three actions: 29 30 1. Choose an index $1 \leq i \lt n$ and swap the values $a_i$ and $a_{i + 1}$. 31 2. Choose an index $1 \leq i \lt n$ and swap the values $b_i$ and $b_{i + 1}$. 32 3. Choose an index $1 \leq i \leq n$ and swap the values $a_i$ and $b_i$. 33 34 You do not need to minimize the number of operations, but the total number must not exceed $1709$. Find any sequence of operations that satisfies both conditions. 35 36 Input 37 38 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The description of the test cases follows. 39 40 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 40$) — the length of the arrays $a$ and $b$. 41 42 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2 \cdot n$). 43 44 The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 2 \cdot n$). 45 46 It is guaranteed that each integer from $1$ to $2 \cdot n$ appears either in array $a$ or in array $b$. 47 48 Output 49 50 For each test case, output the sequence of operations. 51 52 In the first line for each test case, output the number of operations $k$. Note that $0 \leq k \leq 1709$. 53 54 In the following $k$ lines for each test case, output the operations themselves: 55 56 * If you want to swap the values $a_i$ and $a_{i + 1}$, output two integers $1$ and $i$. Note that $1 \leq i \lt n$. 57 * If you want to swap the values $b_i$ and $b_{i + 1}$, output two integers $2$ and $i$. Note that $1 \leq i \lt n$. 58 * If you want to swap the values $a_i$ and $b_i$, output two integers $3$ and $i$. Note that $1 \leq i \leq n$. 59 60 It can be shown that under the given constraints, a solution always exists. 61 62 Example 63 64 Input 65 66 ``` 67 6 68 69 1 70 71 1 72 73 2 74 75 1 76 77 2 78 79 1 80 81 2 82 83 1 3 84 85 4 2 86 87 2 88 89 1 4 90 91 3 2 92 93 3 94 95 6 5 4 96 97 3 2 1 98 99 3 100 101 5 3 4 102 103 2 6 1 104 ``` 105 106 Output 107 108 ``` 109 0 110 1 111 3 1 112 1 113 2 1 114 1 115 3 2 116 9 117 3 1 118 3 2 119 3 3 120 1 1 121 2 1 122 2 2 123 1 2 124 1 1 125 2 1 126 6 127 2 2 128 1 1 129 1 2 130 2 1 131 3 1 132 3 2 133 ``` 134 135 Note 136 137 In the first test case, $a_1 \lt b_1$, so no operations need to be applied. 138 139 In the second test case, $a_1 \gt b_1$. After applying the operation, these values will be swapped. 140 141 In the third test case, after applying the operation, $a = [1, 3]$ and $b = [2, 4]$. 142 143 In the fourth test case, after applying the operation, $a = [1, 2]$ and $b = [3, 4]$.