codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.