← 返回题目列表

Codeforces · 980/C

C. 海报化

中文机器翻译题面 查看原题

易卜拉欣教授已经为他的算法课准备了期末作业。他要求他的学生实现海报化图像过滤器。

他们的算法将在整数数组上进行测试,其中第 $$$i$$$ 个整数表示图像中第 $$$i$$$ 个像素的颜色。图像是黑白的,因此每个像素的颜色将是 0 到 255(含)之间的整数。

为了实现过滤器,学生需要将黑白颜色范围 [0, 255] 分成连续颜色组,并在每组中选择一种颜色作为该组的关键。为了保留图像细节,组的大小不得大于$$$k$$$,并且每种颜色应该恰好属于一个组。

最后,学生将用该颜色指定的组键替换数组中每个像素的颜色。

为了更好地理解效果,这里有一张姥龟的图像,其中应用了色调分离滤镜,并向右增加 $$$k$$$。

为了使检查最终答案的过程变得更容易,易卜拉欣教授希望学生分组并以产生字典顺序最小可能数组的方式分配键。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq k \leq 256$$$),分别是图像中的像素数和组的最大大小。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$0 \leq p_i \leq 255$$$),其中 $$$p_i$$$ 是第 $$$i$$$ 个像素的颜色。

输出

打印 $$$n$$$ 空格分隔的整数;按字典顺序排列的最小可能数组,表示应用色调分离滤镜后的图像。

示例

输入 #1

4 3
2 14 3 4

输出 #1

0 12 3 3

输入 #2

5 2
0 2 1 255 254

输出 #2

0 1 1 254 254

注意

对第一个样本进行颜色分组和分配键的一种可能方法:

颜色 $$$2$$$ 属于组 $$$[0,2]$$$,组键为 $$$0$$$。

颜色 $$$14$$$ 属于组 $$$[12,14]$$$,组密钥为 $$$12$$$。

颜色 $$$3$$$ 和 $$$4$$$ 属于组 $$$[3, 5]$$$,组密钥为 $$$3$$$。

其他组不会影响结果,因此此处未列出。