← 返回题目列表

Codeforces · 1154/E

E. 两队

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

有 $$$n$$$ 名学生站成一排。两名教练组成两队——第一位教练选择第一队,第二位教练选择第二队。

第 $$$i$$$ 位学生具有整数编程技能 $$$a_i$$$。所有编程技能都是不同的,并且介于 $$$1$$$ 和 $$$n$$$ 之间(包含这两者)。

首先,第一位教练会在所有未进入任何团队的学生中选择编程能力最高的学生,以及离他左边最近的$$$k$$$个学生和离他右边最近的$$$k$$$个学生(如果左边或右边少于$$$k$$$个学生,则全部选择)。所有被选中的学生都离开队列并加入第一队。其次,第二个教练也会做出同样的动作(但他选择的所有学生都加入第二队)。然后第一位教练会再次做出这样的举动,依此类推。重复此操作,直到该行变空(即当每个学生加入某个团队时该过程结束)。

你的问题是确定哪些学生将被纳入第一队,哪些学生将被纳入第二队。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — 分别是学生数量和每次移动期间确定所选学生范围的值。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个学生的编程技能。保证所有编程技能都是独特的。

输出

打印 $$$n$$$ 个字符的字符串;如果第 $$$i$$$ 个学生加入第一队,则第 $$$i$$$ 个字符应为 1,否则为 2。

示例

输入 #1

5 2
2 4 5 3 1

输出 #1

11111

输入 #2

5 1
2 1 3 5 4

输出 #2

22111

输入 #3

7 1
7 2 1 3 5 4 6

输出 #3

1121122

输入#4

5 1
2 4 5 3 1

输出#4

21112

注意

在第一个示例中,第一位教练选择位置为 $$$3$$$ 的学生,并且该行变为空(所有学生都加入第一队)。

在第二个示例中,第一位教练选择位置为 $$$4$$$ 的学生,该行变为 $$$[2, 1]$$$(具有编程技能 $$$[3, 4, 5]$$$ 的学生加入第一队)。然后第二个教练选择位置为 $$$1$$$ 的学生,该行变为空(具有编程技能 $$$[1, 2]$$$ 的学生加入第二队)。

在第三个示例中,第一位教练选择位置为 $$$1$$$ 的学生,该行变为 $$$[1, 3, 5, 4, 6]$$$(具有编程技能的学生 $$$[2, 7]$$$ 加入第一队)。然后第二个教练选择位置$$$5$$$的学生,该行变为$$$[1, 3, 5]$$$(具有编程技能的学生$$$[4, 6]$$$加入第二队)。然后第一位教练选择位置为$$$3$$$的学生,该行变为$$$[1]$$$(具有编程技能$$$[3, 5]$$$的学生加入第一队)。然后第二个教练选择剩下的学生(具有编程技能 $$$1$$$ 的学生加入第二个团队)。

在第四个示例中,第一位教练选择位置为 $$$3$$$ 的学生,该行变为 $$$[2, 1]$$$(具有编程技能 $$$[3, 4, 5]$$$ 的学生加入第一队)。然后第二个教练选择位置为 $$$1$$$ 的学生,该行变为空(具有编程技能 $$$[1, 2]$$$ 的学生加入第二队)。