B2. Wonderful Coloring

Wonderful Coloring"/>

B2. Wonderful Coloring

题目：

This problem is an extension of the problem “Wonderful Coloring - 1”. It has quite many differences, so you should read this statement completely.

Recently, Paul and Mary have found a new favorite sequence of integers a1,a2,…,an. They want to paint it using pieces of chalk of k colors. The coloring of a sequence is called wonderful if the following conditions are met:

each element of the sequence is either painted in one of k colors or isn’t painted;
each two elements which are painted in the same color are different (i. e. there’s no two equal values painted in the same color);
let’s calculate for each of k colors the number of elements painted in the color — all calculated numbers must be equal;
the total number of painted elements of the sequence is the maximum among all colorings of the sequence which meet the first three conditions.
E. g. consider a sequence a=[3,1,1,1,1,10,3,10,10,2] and k=3. One of the wonderful colorings of the sequence is shown in the figure.

The example of a wonderful coloring of the sequence a=[3,1,1,1,1,10,3,10,10,2] and k=3. Note that one of the elements isn’t painted.
Help Paul and Mary to find a wonderful coloring of a given sequence a.

Input
The first line contains one integer t (1≤t≤10000) — the number of test cases. Then t test cases follow.

Each test case consists of two lines. The first one contains two integers n and k (1≤n≤2⋅105, 1≤k≤n) — the length of a given sequence and the number of colors, respectively. The second one contains n integers a1,a2,…,an (1≤ai≤n).

It is guaranteed that the sum of n over all test cases doesn’t exceed 2⋅105.

Output
Output t lines, each of them must contain a description of a wonderful coloring for the corresponding test case.

Each wonderful coloring must be printed as a sequence of n integers c1,c2,…,cn (0≤ci≤k) separated by spaces where

ci=0, if i-th element isn’t painted;
ci>0, if i-th element is painted in the ci-th color.
Remember that you need to maximize the total count of painted elements for the wonderful coloring. If there are multiple solutions, print any one.

Example
input
6
10 3
3 1 1 1 1 10 3 10 10 2
4 4
1 1 1 1
1 1
1
13 1
3 1 4 1 5 9 2 6 5 3 5 8 9
13 2
3 1 4 1 5 9 2 6 5 3 5 8 9
13 3
3 1 4 1 5 9 2 6 5 3 5 8 9
output
1 1 0 2 3 2 2 1 3 3
4 2 1 3
1
0 0 1 1 0 1 1 1 0 1 1 1 0
2 1 2 2 1 1 1 1 2 1 0 2 2
1 1 3 2 1 3 3 1 2 2 3 2 0

。。一个简单题写半天没写好。。。

解题思路：
记录每一个数量不超过k的数字的下标，统计k种颜色一共能有多少种能染多少次，，然后挨个循环给每种数字染不同的颜色知道染完为止，颜色通过%来重置

AC代码：

#include <iostream>
#include <cstring>
#include <vector>
#include <map>
using namespace std;int n, k;
int ans[200020];
map<int, vector<int>> mp;int main() {ios_base::sync_with_stdio(false);int t;cin >> t;while (t--) {int n, k;cin >> n >> k;memset(ans, 0, (n+1) * sizeof(ans[0]));mp.clear();for (int i = 1; i <= n; i++) {int c;cin >> c;if(mp[c].size() < k) mp[c].push_back(i);}int m = 0;for (auto e : mp) m += e.second.size();m -= m % k;int color = 0;for(auto e:mp)for (auto i : e.second) {ans[i] = ++color;color %= k;if (--m == 0) goto output;}output:for (int i = 1; i <= n; i++)cout << ans[i] << ' ';cout << '\n';}return 0;
}