1903B.md (2115B)
1 Source: https://codeforces.com/problemset/problem/1903/B 2 3 B. StORage room 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 In Cyprus, the weather is pretty hot. Thus, Theofanis saw this as an opportunity to create an ice cream company. 22 23 He keeps the ice cream safe from other ice cream producers by locking it inside big storage rooms. However, he forgot the password. Luckily, the lock has a special feature for forgetful people! 24 25 It gives you a table $M$ with $n$ rows and $n$ columns of non-negative integers, and to open the lock, you need to find an array $a$ of $n$ elements such that: 26 27 * $0 \le a_i \lt 2^{30}$, and 28 * $M_{i,j} = a_i | a_j$ for all $i \neq j$, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). 29 30 The lock has a bug, and sometimes it gives tables without any solutions. In that case, the ice cream will remain frozen for the rest of eternity. 31 32 Can you find an array to open the lock? 33 34 Input 35 36 The first line contains a single integer $t$ ($1 \le t \le 10^{3}$) — the number of test cases. 37 38 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^{3}$) — the size of the hidden array. 39 40 The next $n$ lines describe the rows of $M$, line $i$ contains the table values $M_{i,1}, M_{i,2}, \ldots, M_{i,n}$ ($0 \le M_{i,j} \lt 2^{30}$). 41 42 It is guaranteed that $M_{i,i} = 0$ and $M_{i,j} = M_{j,i}$ for all $1 \le i,j \le n$. 43 44 It is also guaranteed that the sum of $n$ over all test cases does not exceed $10^{3}$. 45 46 Output 47 48 For each test case, if there is a solution print YES and an array that satisfies the property, otherwise print NO. 49 50 If there are multiple solutions, print any of them. 51 52 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. 53 54 Example 55 56 Input 57 58 ``` 59 4 60 61 1 62 63 0 64 65 4 66 67 0 3 3 5 68 69 3 0 3 7 70 71 3 3 0 7 72 73 5 7 7 0 74 75 5 76 77 0 7 7 5 5 78 79 7 0 3 2 6 80 81 7 3 0 3 7 82 83 5 2 3 0 4 84 85 5 6 7 4 0 86 87 3 88 89 0 0 1 90 91 0 0 0 92 93 1 0 0 94 ``` 95 96 Output 97 98 ``` 99 YES 100 7 101 YES 102 1 3 2 5 103 YES 104 5 2 3 0 4 105 NO 106 ```