AT_abc260_d [ABC260D] Draw Your Cards

题目描述

有一叠写有 $1$ 到 $N$ 的 $N$ 张卡牌，背面朝上叠放成一堆，从上往下第 $i$ 张卡牌上写着整数 $P_i$。

你需要用这叠卡牌进行如下操作，共进行 $N$ 回合：

• 从牌堆顶抽出一张卡牌，记其上写的整数为 $X$。
• 在场上所有正面朝上的卡牌中，找出所有写着整数大于等于 $X$ 的卡牌，选择其中写着整数最小的那一张，把刚抽出的卡牌正面朝上叠在它上面。如果没有这样的卡牌，则将抽出的卡牌正面朝上单独放在场上。
• 然后，如果场上有某一堆正面朝上的卡牌数量达到 $K$ 张，则把这堆卡牌全部“吃掉”，即从场上移除。

请你求出每张卡牌在第几回合被吃掉，如果直到最后都没有被吃掉，则输出 $-1$。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

输出 $N$ 行。
第 $i$ 行输出如下内容，表示写有整数 $i$ 的卡牌的情况：

• 如果第 $i$ 张卡牌被吃掉，输出其被吃掉的回合数（整数）。
• 否则输出 $-1$。

输入输出样例 #1

输入 #1

5 2
3 5 2 1 4

输出 #1

4
3
3
-1
4

输入输出样例 #2

输入 #2

5 1
1 2 3 4 5

输出 #2

1
2
3
4
5

输入输出样例 #3

输入 #3

15 3
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

输出 #3

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15

说明/提示

限制条件

• 所有输入均为整数。
• $1 \leq K \leq N \leq 2 \times 10^5$
• $P$ 是 $1,2,\dots,N$ 的一个排列（即 $P$ 是 $1,2,\dots,N$ 的重排）。

样例解释 1

本例中，$P=(3,5,2,1,4), K=2$。

• 第 $1$ 回合，抽出写有 $3$ 的卡牌，场上没有其他卡牌，将其正面朝上放在场上。
• 第 $2$ 回合，抽出写有 $5$ 的卡牌，场上没有其他卡牌，将其正面朝上放在场上。
• 第 $3$ 回合，抽出写有 $2$ 的卡牌，场上有 $3$，$5$，其中 $3 \geq 2$ 且最小，将 $2$ 叠在 $3$ 上。
• 此时，$2$ 和 $3$ 叠成一堆，堆中有 $K=2$ 张卡牌，将这两张卡牌全部吃掉。
• 第 $4$ 回合，抽出写有 $1$ 的卡牌，场上只剩 $5$，$5 \geq 1$，将 $1$ 叠在 $5$ 上。
• 此时，$1$ 和 $5$ 叠成一堆，堆中有 $K=2$ 张卡牌，将这两张卡牌全部吃掉。
• 第 $5$ 回合，抽出写有 $4$ 的卡牌，场上没有其他卡牌，将其正面朝上放在场上。
• 写有 $4$ 的卡牌直到最后都没有被吃掉。

样例解释 2

当 $K=1$ 时，所有卡牌在被放到场上的回合就会被吃掉。

由 ChatGPT 4.1 翻译