2170C.md (2595B)
1 Source: https://codeforces.com/problemset/problem/2170/C 2 3 C. Quotient and Remainder 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two integer arrays: $q_1, q_2, \dots, q_n$ and $r_1, r_2, \dots, r_n$, as well as an integer $k$. 22 23 You can perform the following operation any number of times (possibly zero): 24 25 1. Choose two integers $x$ and $y$ such that 26 * $1 \le y \lt x \le k$; 27 * there exists an index $i$ such that $q_i = \left\lfloor \frac{x}{y} \right\rfloor$ (rounded down); 28 * there exists an index $j$ such that $r_j = x \bmod y$. 29 2. Remove $q_i$ from the array $q$ and $r_j$ from the array $r$. If there are multiple occurrences of $q_i$ in the array $q$, only one occurrence is removed; same for $r_j$ and the array $r$. 30 31 Calculate the maximum number of operations that you can perform on the given arrays $q$ and $r$. 32 33 Input 34 35 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 36 37 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $2 \le k \le 10^{18}$) — the size of the arrays $q$ and $r$ and the upper limit for $x$ and $y$. 38 39 The second line of each test case contains $n$ integers $q_1, q_2, \dots, q_n$ ($1 \le q_i \le 10^9$) — the array $q$. 40 41 The third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^9$) — the array $r$. 42 43 Additional constraints on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, print one integer — the maximum number of operations that you can perform on the given arrays. 48 49 Example 50 51 Input 52 53 ``` 54 3 55 56 1 100 57 58 1 59 60 27 61 62 3 10 63 64 5 6 5 65 66 7 1 7 67 68 5 42 69 70 5 4 2 2 1 71 72 9 8 9 8 100 73 ``` 74 75 Output 76 77 ``` 78 1 79 80 0 81 82 3 83 ``` 84 85 Note 86 87 In the first test case, one operation can be performed: you can choose $x = 69$ and $y = 42$. Then $\left\lfloor \frac{69}{42} \right\rfloor = 1 = q_1$ and $69 \bmod 42 = 27 = r_1$. 88 89 In the second test case, it is impossible to perform any operations, as suitable $x$ and $y$ cannot be found. 90 91 In the third test case, three operations can be performed: 92 93 1. $x = 42$, $y = 17$: $\left\lfloor \frac{42}{17} \right\rfloor = 2 = q_3$ and $42 \bmod 17 = 8 = r_2$; 94 2. $x = 41$, $y = 16$: $\left\lfloor \frac{41}{16} \right\rfloor = 2 = q_4$ and $41 \bmod 16 = 9 = r_1$; 95 3. $x = 20$, $y = 12$: $\left\lfloor \frac{20}{12} \right\rfloor = 1 = q_5$ and $20 \bmod 12 = 8 = r_4$; 96 97 After these operations, you'll get arrays $q = [5, 4]$ and $r = [9, 100]$, and there are no more operations you can perform.