← 返回题目列表

Codeforces · 1041/C

C. 茶歇

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

最近 Monocarp 找到了工作。他的工作日正好持续 $$$m$$$ 分钟。在工作期间,Monocarp 希望在某些时刻喝咖啡:有 $$$n$$$ 分钟 $$$a_1, a_2, \dots, a_n$$$,当他能够并且愿意喝咖啡休息时(为了简单起见,我们假设每次喝咖啡休息时间恰好为一分钟)。

然而,Monocarp 的老板不喜欢 Monocarp 太频繁地喝咖啡休息。因此,对于给定的咖啡休息时间 $$$a_i$$$ 分钟,Monocarp 必须选择在该分钟内喝咖啡的日期,以便每天任意两个咖啡休息时间之间至少经过 $$$d$$$ 分钟。 Monocarp 还希望在尽可能少的工作日内享受这些$$$n$$$ 的咖啡休息时间(他不计算他不工作的天数,并且在这些日子里他也不喝咖啡休息时间)。考虑到任何工作日结束和下一个工作日开始之间经过的时间超过 $$$d$$$ 分钟。

对于给定的每个 $$$n$$$ 分钟,确定 Monocarp 应该在这一分钟内喝咖啡休息的日期。您必须尽量减少花费的天数。

输入

第一行包含三个整数 $$$n$$$, $$$m$$$, $$$d$$$ $$$(1 \le n \le 2\cdot10^{5}, n \le m \le 10^{9}, 1 \le d \le m)$$$ — Monocarp 想要的咖啡休息次数、每个工作日的长度和最少分钟数任意两次连续喝咖啡的休息时间之间。

第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le m)$$$,其中 $$$a_i$$$ 是 Monocarp 想要喝咖啡休息时的某一分钟。

输出

在第一行中,在给定的 $$$n$$$ 分钟内写下喝咖啡休息所需的最少天数。

在第二行中,打印 $$$n$$$ 空格分隔的整数。第 $$$i$$$ 整数应该是一天中 Monocarp 在 $$$a_i$$$ 分钟喝咖啡休息的索引。天数从 $$$1$$$ 开始编号。如果有多个最优解,可以打印任意一个。

示例

输入 #1

4 5 3
3 5 1 2

输出 #1

3
3 1 1 2

输入 #2

10 10 1
10 5 7 4 6 3 2 1 9 8

输出 #2

2
2 1 1 2 2 1 2 1 1 2

注意

在第一个示例中,Monocarp 在第一天可以休息两次(在 $$$1$$$ 和 $$$5$$$ 分钟内,这些休息之间将经过 $$$3$$$ 分钟)。第二天休息一次($$$2$$$ 分钟),第三天休息一次($$$3$$$ 分钟)。

在第二个例子中,Monocarp可以如下确定休息的日期:如果他想要休息的分钟是奇数,那么这次休息是在第一天,如果是偶数,那么这次休息是在第二天。