C_you are given an array aa consisting of nn integer

You are given an array aa

consisting of nn

integer numbers.You have to color this array in kk

colors in such a way that: Each element of the array should be colored in some color; For each ii

from 11

to kk

there should be at least one element colored in the ii

-th color in the array; For each ii

from 11

to kk

all elements colored in the ii

-th color should be distinct. Obviously, such coloring might be impossible. In this case, print “NO”. Otherwise print “YES” and any coloring (i.e. numbers c1,c2,…cnc1,c2,…cn

, where 1≤ci≤k1≤ci≤k

and cici

is the color of the ii

-th element of the given array) satisfying the conditions above. If there are multiple answers, you can print any.InputThe first line of the input contains two integers nn

and kk

(1≤k≤n≤50001≤k≤n≤5000

) — the length of the array aa

and the number of colors, respectively.The second line of the input contains nn

integers a1,a2,…,ana1,a2,…,an

(1≤ai≤50001≤ai≤5000

) — elements of the array aa

.OutputIf there is no answer, print “NO”. Otherwise print “YES” and any coloring (i.e. numbers c1,c2,…cnc1,c2,…cn

, where 1≤ci≤k1≤ci≤k

and cici

is the color of the ii

-th element of the given array) satisfying the conditions described in the problem statement. If there are multiple answers, you can print any.Examples Input 4 2
1 2 2 3
Output YES
1 1 2 2
Input 5 2
3 2 1 2 3
Output YES
2 1 1 2 1
Input 5 2
2 1 1 2 1
Output NO
NoteIn the first example the answer 2 1 2 12 1 2 1

is also acceptable.In the second example the answer 1 1 1 2 21 1 1 2 2

is also acceptable.There exist other acceptable answers for both examples.

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
int n, k,b[5100];
struct student
{
    int shu, zhi,id;
} a[5100];
int cmp1(student x, student y)
{
    return (x.shu < y.shu);
}
int cmp2(student x, student y)
{
    return (x.id < y.id);
}
int main()
{
    scanf("%d %d",&n,&k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&a[i].shu);
        b[a[i].shu]++;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp1);
    int maxx = 0;
    for (int i = 1; i <= 5000; i++)
        maxx = max(b[i],maxx);
    if (maxx > k)
    {
        printf("NO\n");
        return 0;
    }
    int kk = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i].zhi = kk % k + 1;
        kk++;
    }
    sort(a + 1, a + n + 1, cmp2);
    printf("YES\n");
    for (int i = 1; i <= n; i++)
    {
        if (i == 1)
            printf("%d",a[i].zhi);
        else
            printf(" %d",a[i].zhi);
    }
    printf("\n");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

#include <bits/stdc++.h>
using namespace std;
int k,n;
struct node
{
    int x,id,ans; //x为数字,id为输入顺序,ans为颜色
}a[5005];
bool cmp1(node x,node y) //第一次按数字排序
{
    return x.x<y.x;
}
bool cmp2(node x,node y) //第二次按输入顺序排序
{
    return x.id<y.id;
}
int main()
{
    scanf("%d%d",&n,&k);
    if(n<k) //颜色比格子多，不可能全部用上
    {
        puts("NO");
        return 0;
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].x),a[i].id=i;
    sort(a+1,a+1+n,cmp1);
    int start=0,color=0; //start为某种数字首次出现的位置,color为当前要填的颜色
    for(int i=1;i<=n;i++)
    {
        if(++color>k) color-=k; //换一种颜色,太大了就回到第一种颜色
        a[i].ans=color; //填色
        if(a[i].x==a[i-1].x)
        {
            if(i-start+1>k) //减一减得到已经填了几个该种相同数字，是否大于颜色数
            {
                puts("NO");
                return 0;
            }   
        }
        else start=i; //新数字,新起点
    }
    puts("YES");
    sort(a+1,a+1+n,cmp2); //按输入顺序重排一次
    for(int i=1;i<=n;i++)
        printf("%d ",a[i].ans); //输出
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46