310821: CF1894B. Two Out of Three
Description
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:
- There exist indices $1 \leq i, j \leq n$ such that $a_i = a_j$, $b_i = 1$, $b_j = 2$.
- There exist indices $1 \leq i, j \leq n$ such that $a_i = a_j$, $b_i = 1$, $b_j = 3$.
- There exist indices $1 \leq i, j \leq n$ such that $a_i = a_j$, $b_i = 2$, $b_j = 3$.
If such an array does not exist, you should report it.
InputEach 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.
The first line of each test case contains an integer $n$ $(1 \leq n \leq 100)$ — the length of the array $a$.
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$.
OutputFor 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.
ExampleInput9 6 1 2 3 2 2 3 7 7 7 7 7 7 7 7 4 1 1 2 2 7 1 2 3 4 5 6 7 5 2 3 3 3 2 3 1 2 1 9 1 1 1 7 7 7 9 9 9 1 1 18 93 84 50 21 88 52 16 50 63 1 30 85 29 67 63 58 37 69Output
1 2 3 1 1 1 -1 3 2 2 1 -1 2 1 2 1 3 -1 1 1 2 2 1 2 2 3 3 -1 3 2 1 3 3 3 3 2 2 1 1 2 3 1 3 1 1 2Note
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.
Output
1. 存在索引 \(1 \leq i, j \leq n\) 使得 \(a_i = a_j\),\(b_i = 1\),\(b_j = 2\)。
2. 存在索引 \(1 \leq i, j \leq n\) 使得 \(a_i = a_j\),\(b_i = 1\),\(b_j = 3\)。
3. 存在索引 \(1 \leq i, j \leq n\) 使得 \(a_i = a_j\),\(b_i = 2\),\(b_j = 3\)。
如果这样的数组不存在,应该报告它。
输入数据格式:每个测试包含多个测试用例。第一行包含一个整数 \(t\)(\(1 \leq t \leq 500\))——测试用例的数量。每个测试用例描述如下:
- 每个测试用例的第一行包含一个整数 \(n\)(\(1 \leq n \leq 100\))——数组 \(a\) 的长度。
- 每个测试用例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)(\(1 \leq a_i \leq 100\))——数组 \(a\) 的元素。
输出数据格式:对于每个测试用例,如果不存在解决方案,则打印 -1。否则,打印 \(b_1, b_2, \ldots, b_n\)——一个由数字 1、2、3 组成的数组,满足上述三个条件中的恰好两个。如果存在多个可能的答案,可以打印其中任何一个。题目大意:给定一个数组 \(a_1, a_2, \ldots, a_n\),需要找到一个数组 \(b_1, b_2, \ldots, b_n\),由数字 1、2、3 组成,使得以下三个条件中有且仅有两个被满足: 1. 存在索引 \(1 \leq i, j \leq n\) 使得 \(a_i = a_j\),\(b_i = 1\),\(b_j = 2\)。 2. 存在索引 \(1 \leq i, j \leq n\) 使得 \(a_i = a_j\),\(b_i = 1\),\(b_j = 3\)。 3. 存在索引 \(1 \leq i, j \leq n\) 使得 \(a_i = a_j\),\(b_i = 2\),\(b_j = 3\)。 如果这样的数组不存在,应该报告它。 输入数据格式:每个测试包含多个测试用例。第一行包含一个整数 \(t\)(\(1 \leq t \leq 500\))——测试用例的数量。每个测试用例描述如下: - 每个测试用例的第一行包含一个整数 \(n\)(\(1 \leq n \leq 100\))——数组 \(a\) 的长度。 - 每个测试用例的第二行包含 \(n\) 个整数 \(a_1, a_2, \ldots, a_n\)(\(1 \leq a_i \leq 100\))——数组 \(a\) 的元素。 输出数据格式:对于每个测试用例,如果不存在解决方案,则打印 -1。否则,打印 \(b_1, b_2, \ldots, b_n\)——一个由数字 1、2、3 组成的数组,满足上述三个条件中的恰好两个。如果存在多个可能的答案,可以打印其中任何一个。