-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path1551C B2. Wonderful Coloring - 2.cpp
150 lines (146 loc) · 4.53 KB
/
1551C B2. Wonderful Coloring - 2.cpp
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
/*
problem link: https://codeforces.com/contest/1551/problem/B2
my solution on codeforces : https://codeforces.com/contest/1551/submission/191040101
problem name: B1. Wonderful Coloring - 2
status: accepted
author: LELLO
*/
#include <bits/stdc++.h>
#include <iostream>
#include <chrono>
#include <vector>
#include <set>
#include <map>
#include<math.h>
#include <stack>
#include <cmath>
#include <unordered_map>
#include <algorithm>
#include <iomanip>
#include <bitset>
#include <utility>
#include <string>
#include <cctype>
#include <iomanip>
#include <numeric> // for NTH
#define bye return;
#define endl '\n'
#define ll long long
#define li long int
#define lli long long int
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((x).size())
#define ison(num, bit) (num & (1 << bit))
#define setoffif(num, bit) (num ^= (1 << bit)) // iff (num &(1<<bit))
#define setoff(num, bit) (num &= ~(1 << bit))
#define seton(num, bit) (num |= (1 << bit))
#define flipbit(num, bit) (num ^= (1 << bit))
#define LSB(num) (num & (-num))
#define pop_count_int(num) __builtin_popcount(num)
#define pop_count_l(num) __builtin_popcountl(num)
#define pop_count_ll(num) __builtin_popcountll(num)
#define clz(num) __builtin_clz(num)
#define clzll(num) __builtin_clzll(num)
#define ctz(num) __builtin_ctz(num)
#define ctzll __builtin_ctzll
#define Num_of_Digits(n) ((ll)log10(n) + 1)
#define ceill(n, m) (((n) / (m)) + (((n) % (m) ) ? 1 : 0))
#define lastOne(x) (__builtin_clzll(x))
#define fixed(n) fixed << setprecision(n)
#define lb(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define ub(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define Time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << "\n";
#define Pi 3.14159265358979323846264
#define INF 0x3f3f3f3f
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
ll sgn(ll x){ if(x > 0) return 1; if(x < 0) return -1; return 0;}
ll mod = 1e9 + 7;
ll mul(ll a, ll b) { return ((a % mod) * (b % mod)) % mod; }
ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
using namespace std;
void AC() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr); // or cin.tie(NULL)
cout.tie(nullptr); // or cout.tie(0)
}
void file_set(){ //string& file_name
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
// freopen((file_name+".in").c_str(), "r", stdin);
// freopen((file_name+".out").c_str(), "w", stdout);
}
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
return (a.second < b.second);
}
// THOSE WHO CAN'T REMEMBER THE PAST'RE CONDEMNED TO REPEAT IT (USE DP -_-) - George Santayana
// PUSH HARDER THAN YESTERDAY IF YOU WANT A DIFFERENT TOMORROW !
//YOU DON'T HAVE TO BE A GENIUS , YOU NEED TO BE DETERMINED .
const ll int MAX = 6e6;
ll int dp[MAX] ;
const ll LOO = 0x3f3f3f3f3f3f3f3f;
const int OO = 0x3f3f3f3f;
void LELLO(){
ll n , k ; cin >> n >> k ;
vector<ll> vc(n);
vector<ll> ans(n);
unordered_map<ll , vector<ll>> pos ;
for (int i = 0; i < n; i++)
{
cin >> vc[i];
pos[vc[i]].push_back(i) ;
}
ll color = 1 , allsz(0);
for(auto& [key , positions] : pos ){
ll temp = positions.size() ;
allsz += min( temp , k);
if(positions.size() >= k){
for (int i = 0; i < positions.size() ; i++)
{
ans[positions[i]] = ((i < k)? i+1 : -1 );
}
}else{
for (int i = 0; i < positions.size() ; i++)
{
ans[positions[i]] = color++;
if(color == k+1) color = 1 ;
}
}
}
vector<ll> freq(k+1);
for(auto& i : ans ){
if(i == -1) i = 0 ;
freq[i]++;
if(freq[i] > allsz/k) i = 0 ;
}
for (int i = 0; i < ans.size(); i++)
{
cout << ans[i] << ' ' ;
}
cout<<endl;
}
void driver(ll t=1)
{
while (t--) LELLO();
Time
}
signed main()
{
AC();
// file_set();
ll test ; cin >> test ;
// chrono::time_point<chrono::system_clock> start, end;
// start = chrono::system_clock::now();
driver(test);
// end = chrono::system_clock::now();
// chrono::duration<double> elapsed_seconds = end - start;
// time_t end_time = chrono::system_clock::to_time_t(end);
// cout << "finished computation at " << ctime(&end_time) << "elapsed time: " << elapsed_seconds.count() << "s\n";
}