USACO 2024 US Open Contest, Silver - Problem 1: Bessie's Interview

问题描述

Bessie正在寻找一份新工作！幸运的是，有$K$个农场主目前正在招聘并进行面试。由于工作竞争激烈，农场主们决定按照申请的顺序给奶牛编号并进行面试。在Bessie之前有$N$头奶牛申请，所以她的编号是$N + 1$（$1 \leq K \leq N \leq 3 \cdot 10^5$）。

面试过程如下。在时间$0$时，对于每个$1 \leq i \leq K$，农场主$i$将开始面试奶牛$i$。一旦一个农场主完成一次面试，他将立即开始面试下一头排队的奶牛。如果多个农场主同时完成面试，下一头奶牛可以根据自己的偏好选择由任何一个可用的农场主进行面试。

对于每个$1 \leq i \leq N$，Bessie已经知道奶牛$i$的面试将恰好花费$t_i$分钟（$1 \leq t_i \leq 10^9$）。然而，她不知道每头奶牛对农场主的偏好。

由于这份工作对Bessie非常重要，她想仔细准备面试。为此，她需要知道自己什么时候会被面试以及哪些农场主有可能面试她。帮助她找到这些信息！

输入格式（从终端/标准输入读取输入）

• 输入的第一行将包含两个整数$N$和$K$。
• 第二行将包含$N$个整数$t_1 \ldots t_N$。

输出格式（将输出打印到终端/标准输出）

• 在第一行，打印Bessie面试开始的时间。
• 在第二行，一个长度为$K$的位串，如果农场主$i$可能面试Bessie，则第$i$位为$1$，否则为$0$。

示例输入

6 3
3 1 4159 2 6 5

示例输出

8
110

有6头奶牛在Bessie之前，3个农场主，面试过程如下： 在时间$t = 0$时，农场主1面试奶牛1，农场主2面试奶牛2，农场主3面试奶牛3。 在时间$t = 1$时，农场主2完成与奶牛2的面试并开始面试奶牛4。 在时间$t = 3$时，农场主1和农场主2都完成了面试，有两种可能性：

• 农场主1面试奶牛5，农场主2面试奶牛6。在这种情况下，农场主2将在时间$t = 8$完成面试并开始面试Bessie。
• 农场主1面试奶牛6，农场主2面试奶牛5。在这种情况下，农场主1将在时间$t = 8$完成面试并开始面试Bessie。 因此，Bessie的面试将在时间$t = 8$开始，她可能由农场主1或农场主2面试。

评分

• 输入2 - 3：没有两个农场主同时完成面试。
• 输入4 - 9：$N \leq 3 \cdot 10^3$。
• 输入10 - 21：无额外限制。

问题提供者：Avnith Vijayram