codeforces-scrape

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

1681C.md (1596B)


      1 Source: https://codeforces.com/problemset/problem/1681/C
      2 
      3 C. Double Sort
      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 $a$ and $b$, both consisting of $n$ integers.
     22 
     23 In one move, you can choose two indices $i$ and $j$ ($1 \le i, j \le n$; $i \neq j$) and swap $a_i$ with $a_j$ and $b_i$ with $b_j$. You have to perform the swap in both arrays.
     24 
     25 You are allowed to perform at most $10^4$ moves (possibly, zero). Can you make both arrays sorted in a non-decreasing order at the end? If you can, print any sequence of moves that makes both arrays sorted.
     26 
     27 Input
     28 
     29 The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of testcases.
     30 
     31 The first line of each testcase contains a single integer $n$ ($2 \le n \le 100$) — the number of elements in both arrays.
     32 
     33 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the first array.
     34 
     35 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) — the second array.
     36 
     37 Output
     38 
     39 For each testcase, print the answer. If it's impossible to make both arrays sorted in a non-decreasing order in at most $10^4$ moves, print -1. Otherwise, first, print the number of moves $k$ $(0 \le k \le 10^4)$. Then print $i$ and $j$ for each move $(1 \le i, j \le n$; $i \neq j)$.
     40 
     41 If there are multiple answers, then print any of them. You don't have to minimize the number of moves.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 2
     51 
     52 1 2
     53 
     54 1 2
     55 
     56 2
     57 
     58 2 1
     59 
     60 1 2
     61 
     62 4
     63 
     64 2 3 1 2
     65 
     66 2 3 2 3
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 0
     73 -1
     74 3
     75 3 1
     76 3 2
     77 4 3
     78 ```