670 . 到底隊不隊

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

88.9% (8/9)

Tags

apcsc apcsc-ds

Description

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

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

現在，給你 N、K、和所有的 ai 的值，你可以寫一支程式輸出誰在第幾隊嗎？

Input Format

輸入將有兩行。第一行包含兩個數字 N 與 K(1≤K≤N≤2×105)，代表與會人數與題目中提到的常數 K。第二行有 N 個數字，第 i 個數字代表 ai(1≤ai≤N)，且保證 ai 兩兩不重複。

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
Submit
Back to Top