1894B.md (2116B)
1 Source: https://codeforces.com/problemset/problem/1894/B 2 3 B. Two Out of Three 4 5 time limit per test 6 7 3 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 an array $a_1, a_2, \ldots, a_n$. You need to find an array $b_1, b_2, \ldots, b_n$ consisting of numbers $1$, $2$, $3$ such that exactly two out of the following three conditions are satisfied: 22 23 1. There exist indices $1 \leq i, j \leq n$ such that $a_i = a_j$, $b_i = 1$, $b_j = 2$. 24 2. There exist indices $1 \leq i, j \leq n$ such that $a_i = a_j$, $b_i = 1$, $b_j = 3$. 25 3. There exist indices $1 \leq i, j \leq n$ such that $a_i = a_j$, $b_i = 2$, $b_j = 3$. 26 27 If such an array does not exist, you should report it. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 500)$ — the number of test cases. Each test case is described as follows. 32 33 The first line of each test case contains an integer $n$ $(1 \leq n \leq 100)$ — the length of the array $a$. 34 35 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 100)$ — the elements of the array $a$. 36 37 Output 38 39 For each test case, print -1 if there is no solution. Otherwise, print $b_1, b_2, \ldots, b_n$ — an array consisting of numbers $1$, $2$, $3$ that satisfies exactly two out of three conditions. If there are multiple possible answers, you can print any of them. 40 41 Example 42 43 Input 44 45 ``` 46 9 47 48 6 49 50 1 2 3 2 2 3 51 52 7 53 54 7 7 7 7 7 7 7 55 56 4 57 58 1 1 2 2 59 60 7 61 62 1 2 3 4 5 6 7 63 64 5 65 66 2 3 3 3 2 67 68 3 69 70 1 2 1 71 72 9 73 74 1 1 1 7 7 7 9 9 9 75 76 1 77 78 1 79 80 18 81 82 93 84 50 21 88 52 16 50 63 1 30 85 29 67 63 58 37 69 83 ``` 84 85 Output 86 87 ``` 88 1 2 3 1 1 1 89 -1 90 3 2 2 1 91 -1 92 2 1 2 1 3 93 -1 94 1 1 2 2 1 2 2 3 3 95 -1 96 3 2 1 3 3 3 3 2 2 1 1 2 3 1 3 1 1 2 97 ``` 98 99 Note 100 101 In the first test case, $b = [1, 2, 3, 1, 1, 1]$ satisfies condition $1$ because for $i = 4$, $j = 2$: $a_i = a_j$, $b_i = 1$, and $b_j = 2$. It also satisfies condition $2$ because for $i = 6$, $j = 3$: $a_i = a_j$, $b_i = 1$, and $b_j = 3$. However, it does not satisfy condition $3$. In total, exactly two out of three conditions are satisfied.