1774D.md (2187B)
1 Source: https://codeforces.com/problemset/problem/1774/D 2 3 D. Same Count One 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 ChthollyNotaSeniorious received a special gift from AquaMoon: $n$ binary arrays of length $m$. AquaMoon tells him that in one operation, he can choose any two arrays and any position $pos$ from $1$ to $m$, and swap the elements at positions $pos$ in these arrays. 22 23 He is fascinated with this game, and he wants to find the minimum number of operations needed to make the numbers of $1$s in all arrays the same. He has invited you to participate in this interesting game, so please try to find it! 24 25 If it is possible, please output specific exchange steps in the format described in the output section. Otherwise, please output $-1$. 26 27 Input 28 29 The first line of the input contains a single integer $t$ ($1 \leq t \leq 2\cdot 10^4$) — the number of test cases. The description of test cases follows. 30 31 The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$, $2 \leq m \leq 10^5$). 32 33 The $i$-th of the following $n$ lines contains $m$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$ $(0 \le a_{i, j} \le 1)$ — the elements of the $i$-th array. 34 35 It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$. 36 37 Output 38 39 For each test case, if the objective is not achievable, output $-1$. 40 41 Otherwise, in the first line output $k$ $(0 \le k \le mn)$ — the minimum number of operations required. 42 43 The $i$-th of the following $k$ lines should contain $3$ integers, $x_i, y_i, z_i$ $(1 \le x_i, y_i \le n, 1 \le z_i \le m)$, which describe an operation that swap $a_{x_i, z_i}, a_{y_i, z_i}$: swap the $z_i$-th number of the $x_i$-th and $y_i$-th arrays. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 52 3 4 53 54 1 1 1 0 55 56 0 0 1 0 57 58 1 0 0 1 59 60 4 3 61 62 1 0 0 63 64 0 1 1 65 66 0 0 1 67 68 0 0 0 69 70 2 2 71 72 0 0 73 74 0 1 75 ``` 76 77 Output 78 79 ``` 80 1 81 2 1 1 82 1 83 4 2 2 84 -1 85 ``` 86 87 Note 88 89 In the first test case, it's enough to do a single operation: to swap the first element in the second and the first rows. The arrays will become $[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$, each of them contains exactly two $1$s.