#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define LOOP(i,s,e) for (int64_t i = (s); i < (e); i++)
#define SCAN(...) if (scanf(__VA_ARGS__) == 0) return EXIT_FAILURE
typedef struct p{
int64_t v;
int64_t i;
} p;
int comp(const void *a, const void *b){
p ca = *((p*)a);
p cb = *((p*)b);
if (ca.v == cb.v) return 0;
if (ca.v < cb.v) return -1;
return 1;
}
int main() {
int64_t n, k;
SCAN("%ld %ld", &n, &k);
p *sorted = (p*) malloc(2 * n * sizeof(p));
LOOP(i, 0, n){
SCAN("%ld", &sorted[i].v);
sorted[i].i=i;
}
qsort(sorted, n, sizeof(p), comp);
int64_t *groups = (int64_t *) malloc((k+1) * sizeof(int64_t));
// group i goes from groups[i] to groups[i+1]
LOOP(i, 1, k)
groups[i] = i;
groups[0] = 0;
groups[k] = n;
int64_t old_smart = 0;
int64_t smart = 0;
// bool retest = false;
LOOP(i, 0, k)
smart += sorted[groups[i]].v * (groups[i+1]-groups[i]);
while (old_smart != smart){
old_smart = smart;
// increase right
for(int64_t i = k-1; i >= 0; i--){
int64_t diff =
- sorted[groups[i]].v * (groups[i+1]-groups[i])
+ sorted[groups[i]].v * (groups[i+1]-groups[i] + 1)
- sorted[groups[i+1]].v * (groups[i+2]-groups[i+1])
+ sorted[groups[i+1]+1].v * (groups[i+2]-groups[i+1] - 1);
// printf("%ld -> %ld : dif = %ld\n", groups[i+1], groups[i+1]+1, diff);
while(diff >= 0 && groups[i+1] < groups[i+2]){
groups[i+1]++;
diff =
- sorted[groups[i]].v * (groups[i+1]-groups[i])
+ sorted[groups[i]].v * (groups[i+1]-groups[i] + 1)
- sorted[groups[i+1]].v * (groups[i+2]-groups[i+1])
+ sorted[groups[i+1]+1].v * (groups[i+2]-groups[i+1] - 1);
// printf("++%ld -> %ld : dif = %ld\n", groups[i+1], groups[i+1]+1, diff);
}
}
// decrease left
// LOOP(i, 1, k){
// int64_t diff =
// - sorted[groups[i]].v * (groups[i+1]-groups[i])
// + sorted[groups[i]-1].v * (groups[i+1]-groups[i] + 1)
// - sorted[groups[i-1]].v * (groups[i]-groups[i-1])
// + sorted[groups[i-1]].v * (groups[i]-groups[i-1] - 1);
// while(diff >= 0 && groups[i-1] < groups[i]){
// groups[i]--;
// diff =
// - sorted[groups[i]].v * (groups[i+1]-groups[i])
// + sorted[groups[i]-1].v * (groups[i+1]-groups[i] + 1)
// - sorted[groups[i-1]].v * (groups[i]-groups[i-1])
// + sorted[groups[i-1]].v * (groups[i]-groups[i-1] - 1);
// }
// }
// get number
smart = 0;
LOOP(i, 0, k)
smart += sorted[groups[i]].v * (groups[i+1]-groups[i]);
// retest = ~retest || (smart != old_smart);
// eraze empty groups
}
int64_t *places = (int64_t*) malloc(n * sizeof(int64_t));
for(int64_t i = k-1; i > 0; i--){
printf("groups[%ld] = %ld, groups[%ld] = %ld\n"i, groups[i], i+1, groups[i+1]);
if (groups[i] == groups[i+1])
groups[i]--;
}
LOOP(g, 0, k){
LOOP(i, groups[g], groups[g+1]){
// printf("%ld ", sorted[i].v);
places[sorted[i].i] = g+1;
}
// printf(" | ");
}
// printf("\n");
LOOP(i, 0, n)
printf("%ld ", places[i]);
printf("\n");
return EXIT_SUCCESS;
}