TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

歡迎來到一年一度的裝弱國際競賽!這裡集結了來自各地的好手,明明一個比一個厲害,卻又一個比一個會裝弱。第一輪是淘汰賽,會將與會的 $N$ 位選手分成兩隊。已知每一個選手有一個「裝弱值」,由左數來第 $i$ 位選手的「裝弱值為」 $a_i(1 \leq a_i \leq N)$,且已知選手們的裝弱值兩兩不相同。將這些選手分隊的流程如下:

  • 首先,裝弱值最高的選手、其左邊 $K$ 個選手、其右邊 $K$ 個選手都會加入第一隊(如果左、右邊不到 $K$ 個人則全數選取),這些人脫隊以後剩下的人依照原本的順序重新站好。
  • 接下來,剩下的裝弱值最高的選手,其左邊 $K$ 個選手、其右邊 $K$ 個選手都會加入第二隊(如果左、右邊不到 $K$ 個人則全數選取),這些人脫隊以後剩下的人依照原本的順序重新站好。
  • 以上的流程會一直持續直到這 $N$ 個人全部都被分到其中一個隊伍。

現在,給你 $N$、$K$、和所有的 $a_i$ 的值,你可以寫一支程式輸出誰在第幾隊嗎?

Input Format

輸入將有兩行。第一行包含兩個數字 $N$ 與 $K(1 \leq K \leq N \leq 2 \times 10^ 5)$,代表與會人數與題目中提到的常數 $K$。第二行有 $N$ 個數字,第 $i$ 個數字代表 $a_i(1 \leq a_i \leq N)$,且保證 $a_i$ 兩兩不重複。

Output Format

請輸出 $N$ 個字元,其中第 $i$ 個代表從左數來第 $i$ 個選手被分到哪一隊。如果這個選手被分到第一隊,請輸出 1;如果她被分到第二隊請輸出 2

Sample Input 1

5 2
1 2 3 4 5

Sample Output 1

22111

Sample Input 2

7 3
6 2 5 7 3 1 4

Sample Output 2

1111111

Sample Input 3

9 1
2 4 6 8 9 7 5 3 1

Sample Output 3

122111211

Hints

Problem Source

TIOJ 1154E - Two Teams

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~24 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2500 262144 65536 1 2
1 2500 262144 65536 1 2
2 2500 262144 65536 1 2
3 2500 262144 65536 2
4 2500 262144 65536 2
5 2500 262144 65536 2
6 2500 262144 65536 2
7 2500 262144 65536 2
8 2500 262144 65536 2
9 2500 262144 65536 2
10 2500 262144 65536 2
11 2500 262144 65536 2
12 2500 262144 65536 2
13 2500 262144 65536 2
14 2500 262144 65536 2
15 2500 262144 65536 2
16 2500 262144 65536 2
17 2500 262144 65536 2
18 2500 262144 65536 2
19 2500 262144 65536 2
20 2500 262144 65536 2
21 2500 262144 65536 2
22 2500 262144 65536 2
23 2500 262144 65536 2
24 2500 262144 65536 2