codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2084C.md (2720B)


      1 Source: https://codeforces.com/problemset/problem/2084/C
      2 
      3 C. You Soared Afar With Grace
      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 a permutation $a$ and $b$ of length $n$$^{\text{∗}}$. You can perform the following operation at most $n$ times:
     22 
     23 * Choose two indices $i$ and $j$ ($1 \le i, j \le n$, $i \ne j$), swap $a_i$ with $a_j$, swap $b_i$ with $b_j$.
     24 
     25 Determine whether $a$ and $b$ can be reverses of each other after operations. In other words, for each $i = 1, 2, \ldots, n$, $a_i = b_{n + 1 - i}$.
     26 
     27 If it is possible, output any valid sequence of operations. Otherwise, output $-1$.
     28 
     29 $^{\text{∗}}$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).
     30 
     31 Input
     32 
     33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     34 
     35 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the permutations.
     36 
     37 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).
     38 
     39 The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$).
     40 
     41 It is guaranteed that $a$ and $b$ are permutations of length $n$.
     42 
     43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, if it is impossible, output $-1$ in the only line. Otherwise, output a single integer $m$ ($0 \le m \le n$) — the number of operations in the first line. In the following $m$ lines, output two integers — the indices $i$ and $j$ ($1 \le i, j \le n$, $i \ne j$) in each operation in order. If there are multiple solutions, print any of them.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 5
     55 
     56 2
     57 
     58 1 2
     59 
     60 1 2
     61 
     62 2
     63 
     64 1 2
     65 
     66 2 1
     67 
     68 4
     69 
     70 1 3 2 4
     71 
     72 2 4 1 3
     73 
     74 5
     75 
     76 2 5 1 3 4
     77 
     78 3 5 4 2 1
     79 
     80 5
     81 
     82 3 1 2 4 5
     83 
     84 1 2 3 4 5
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 -1
     91 0
     92 1
     93 1 2
     94 2
     95 1 2
     96 1 3
     97 -1
     98 ```
     99 
    100 Note
    101 
    102 In the second test case, $b$ is already the reverse of $a$.
    103 
    104 In the third test case, after performing the following operation, $b$ will become the reverse of $a$:
    105 
    106 * Swap $a_1, a_2$ and swap $b_1, b_2$. Now $a = [3, 1, 2, 4]$ and $b = [4, 2, 1, 3]$.
    107 
    108 In the fourth test case, after performing the following operations in order, $b$ will become the reverse of $a$:
    109 
    110 * Swap $a_1, a_2$ and swap $b_1, b_2$. Now $a = [5, 2, 1, 3, 4]$ and $b = [5, 3, 4, 2, 1]$.
    111 * Swap $a_1, a_3$ and swap $b_1, b_3$. Now $a = [1, 2, 5, 3, 4]$ and $b = [4, 3, 5, 2, 1]$.