1102B.md (1904B)
1 Source: https://codeforces.com/problemset/problem/1102/B 2 3 B. Array K-Coloring 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 You are given an array $a$ consisting of $n$ integer numbers. 22 23 You have to color this array in $k$ colors in such a way that: 24 25 * Each element of the array should be colored in some color; 26 * For each $i$ from $1$ to $k$ there should be at least one element colored in the $i$-th color in the array; 27 * For each $i$ from $1$ to $k$ all elements colored in the $i$-th color should be distinct. 28 29 Obviously, such coloring might be impossible. In this case, print "NO". Otherwise print "YES" and any coloring (i.e. numbers $c_1, c_2, \dots c_n$, where $1 \le c_i \le k$ and $c_i$ is the color of the $i$-th element of the given array) satisfying the conditions above. If there are multiple answers, you can print any. 30 31 Input 32 33 The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 5000$) — the length of the array $a$ and the number of colors, respectively. 34 35 The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 5000$) — elements of the array $a$. 36 37 Output 38 39 If there is no answer, print "NO". Otherwise print "YES" and any coloring (i.e. numbers $c_1, c_2, \dots c_n$, where $1 \le c_i \le k$ and $c_i$ is the color of the $i$-th element of the given array) satisfying the conditions described in the problem statement. If there are multiple answers, you can print any. 40 41 Examples 42 43 Input 44 45 ``` 46 4 2 47 1 2 2 3 48 ``` 49 50 Output 51 52 ``` 53 YES 54 1 1 2 2 55 ``` 56 57 Input 58 59 ``` 60 5 2 61 3 2 1 2 3 62 ``` 63 64 Output 65 66 ``` 67 YES 68 2 1 1 2 1 69 ``` 70 71 Input 72 73 ``` 74 5 2 75 2 1 1 2 1 76 ``` 77 78 Output 79 80 ``` 81 NO 82 ``` 83 84 Note 85 86 In the first example the answer $2~ 1~ 2~ 1$ is also acceptable. 87 88 In the second example the answer $1~ 1~ 1~ 2~ 2$ is also acceptable. 89 90 There exist other acceptable answers for both examples.