P16664 [CSPro 25] 计算资源调度器

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。 西西艾弗岛上兴建了一批数据中心，建设了云计算资源平台。小 C 是主管西西艾弗云开发的工程师。西西艾弗云中有大量的计算节点，每个计算节点都有唯一编号。 西西艾弗云分为多个可用区，每个计算节点位于一个特定的可用区。一个可用区中可以有多个计算节点。 西西艾弗云中运行的计算任务分为不同的应用，每个计算任务都有一个应用与之对应，一个应用中可能包括多个计算任务。 每个计算任务由一个特定的计算节点执行，下文中计算任务“运行在某可用区上”意即“运行在某可用区的计算节点上”。不同的计算任务对运行的计算节点的要求不尽相同。有的计算任务需要在指定可用区上运行，有的计算任务要和其它应用的计算任务在同一个可用区上运行， 还有的希望不要和某个应用的计算任务在同一个计算节点上运行。 对于一个计算任务，执行它的计算节点一旦选定便不再更改；在选定计算节点后，该任务对计算节点的要求就不再被考虑， 即使新安排的计算任务使得此前已有的计算任务的要求被违反，也是合法的。 下图示意性地说明了可用区、计算节点、计算任务之间的关系，同时也说明了应用和计算任务的对应关系。 :::align{center}  ::: 一开始，小 C 使用了电子表格程序来统计计算任务的分配情况。随着云上的计算节点和计算任务的不断增多，小 C 被这些奇怪的要求搞得焦头烂额，有的时候还弄错了安排，让客户很不满意。 小 C 找到你，希望你能为他提供一个程序，能够输入要运行的计算任务和对节点的要求，结合西西艾弗云的现有计算节点信息，计算出计算任务应该被安排在哪个计算节点上。

计算任务对计算节点的要求十分复杂而且又不好描述，你对小 C 表示写程序这件事很为难。于是，小 C 进行了调研，将这些需求进行了归纳整理，形成了下面这三种标准需求。在提出需求时，必须从这三种标准需求中选取若干种，每种需求只能有一条。选取多种需求意味着要同时满足这些需求。 - 计算节点亲和性 计算任务必须在指定可用区上运行。 - 计算任务亲和性 计算任务必须和指定应用的计算任务在同一可用区上运行。 该要求对计算任务可以运行的可用区添加了限制。不考虑该任务本身，一个可用区若运行有指定应用的任务，则满足要求。 - 计算任务反亲和性 计算任务不能和指定应用的计算任务在同一个计算节点上运行。 该要求对计算任务可以运行的计算节点添加了限制。不考虑该任务本身，一个计算节点若运行有指定应用的任务，则不满足要求。 当要执行的计算任务多起来，计算任务反亲和性的要求可能很难满足。因此在添加计算任务反亲和性要求时，还要指定这个要求是“必须满足”还是“尽量满足”。 小 C 要求你按照如下方法来分配计算节点：按照计算任务的启动顺序，根据要求，依次为每个计算任务选择计算节点。一旦选择了一个计算节点，就固定下来不再变动，并且在此后的选择中，不再考虑这个计算任务的要求。对每个计算任务，选择计算节点的方法是： 1. 过滤阶段 在这个阶段，先根据计算任务的要求，过滤出所有满足要求的计算节点。如果不存在这样的计算节点，并且指定了计算任务反亲和性要求，并且计算任务反亲和性要求是尽量满足的，那么去掉计算任务反亲和性要求，再过滤一次。如果还不存在，就认为该计算任务的要求无法满足，该计算任务无法分配。 2. 排序阶段 在这个阶段，将过滤后的计算节点按照这个方法排序： 1. 选择此时运行计算任务数量最少的计算节点； 2. 选择编号最小的计算节点。

从标准输入读入数据。 输入的第一行包含两个由空格分隔的正整数 $n$ 和 $m$，分别表示计算节点的数目和可用区的数目。计算节点从 $1$ 到 $n$ 编号，可用区从 $1$ 到 $m$ 编号； 输入的第二行包含 $n$ 个由空格分隔的正整数 $l_1, l_2, \ldots, l_i, \ldots, l_n$，表示编号为 $i$ 的计算节点位于编号为 $l_i$ 的可用区。其中，$0 < l_i \leq m$； 输入的第三行包含一个正整数 $g$，表示计算任务的组数； 接下来的 $g$ 行，每行包含六个由空格分隔的整数 $f_i, a_i, na_i, pa_i, paa_i, paar_i$，表示依次启动的一组计算任务的信息，其中： - $f_i$：表示要接连启动 $f_i$ 个所属应用和要求相同的计算任务，其中 $f_i > 0$； - $a_i$：表示这 $f_i$ 个计算任务所属应用的编号，其中 $0 < a_i \leq A_{max}$（$A_{max}$ 代表最大应用编号）； - $na_i$：表示计算节点亲和性要求，其中 $0 \leq na_i \leq m$。当 $na_i = 0$ 时，表示没有计算节点亲和性要求；否则表示要运行在编号为 $na_i$ 的可用区内的计算节点上； - $pa_i$：表示计算任务亲和性要求，其中 $0 \leq pa_i \leq A_{max}$。当 $pa_i = 0$ 时，表示没有计算任务亲和性要求；否则表示必须和编号为 $pa_i$ 的应用的计算任务在同一个可用区运行； - $paa_i$：表示计算任务反亲和性要求，其中 $0 \leq paa_i \leq A_{max}$。当 $paa_i = 0$ 时，表示没有计算任务反亲和性要求；否则表示不能和编号为 $paa_i$ 的应用的计算任务在同一个计算节点上运行； - $paar_i$：表示计算任务亲和性要求是必须满足还是尽量满足，当 $paa_i = 0$ 时，$paar_i$ 也一定为 $0$；否则 $paar_i = 1$ 表示“必须满足”，$paar_i = 0$ 表示“尽量满足”。 计算任务按组输入实际上是一种简化的记法，启动一组 $(f_i, a_i, na_i, pa_i, paa_i, paar_i)$ 和连续启动 $f_i$ 组 $(1, a_i, na_i, pa_i, paa_i, paar_i)$ 并无不同。

输出到标准输出。 输出 $g$ 行，每行有 $f_i$ 个整数，由空格分隔，分别表示每个计算任务被分配的计算节点的情况。若该计算任务没有被分配，则输出 $0$；否则输出被分配的计算节点的编号。

### 样例 1 解释 本输入中声明了十个计算节点，前五个位于可用区 $1$，后五个位于可用区 $2$。可用区 $3$ 和 $4$ 不包含任何计算节点。 对于第一组计算任务，由于它们声明了计算节点亲和性要求，但要求的可用区编号是 $4$，该可用区不包含计算节点，因此都不能满足。 对于第二组计算任务，要在可用区 $1$ 中启动 $6$ 份应用 $1$ 的任务，并且要求了计算任务反亲和性。因此，前五份任务分别被安排在前五个节点上。对于第六份任务，由于它必须运行于可用区 $1$，所以能够安排的范围仅限于前五个节点。但是它还指定了强制的计算任务反亲和性，前五个节点上已经启动了属于应用 $1$ 的计算任务，因此没有能够运行它的节点。 对于第三组计算任务，要在可用区 $2$ 中启动 $1$ 份应用 $2$ 的任务，直接将其分配给节点 $6$。 对于第四组计算任务，要在可用区 $2$ 中启动 $6$ 份应用 $1$ 的任务，并且要求了计算任务反亲和性，不能和应用 $2$ 的计算任务分配在同一个节点上。因此，节点 $6$ 不能用于分配，这六份任务只能分配在节点 $7 \sim 10$ 上。按照题意，选取运行任务数最少的和编号最小的，因此依次分配 $7、8、9、10、7、8$。 对于第五组计算任务，要在可用区 $2$ 中启动 $5$ 份应用 $2$ 的任务，并且要求了尽量满足的计算任务反亲和性，不能和应用 $1$ 的计算任务分配在同一个节点上。此时，可用区 $2$ 中的节点 $6$ 上没有应用 $1$ 的计算任务，因此这 $5$ 份计算任务都会被分配到这个节点上。 对于第六组计算任务，要启动 $11$ 份应用 $3$ 的任务，并且要求了尽量满足的计算任务反亲和性，不能和应用 $3$ 的其它计算任务分配在同一个节点上，同时要求和应用 $1$ 的计算任务位于同一个可用区。应用 $1$ 位于两个可用区，因此全部 $10$ 个节点都可以用于分配。对于前 $10$ 份任务，按照题意，依次选取运行的任务数最少且编号最小的节点进行分配。对于第 $11$ 份任务，由于所有的节点上都运行有应用 $3$ 的任务，因此没有节点符合它的反亲和性要求。又因为反亲和性要求是尽量满足的，因此可以忽略这一要求，将它安排在节点 $1$ 上。 ### 子任务 本题包含 $20$ 个测试用例，每个 $5$ 分。 全部测试数据保证 $0 < m \leq n \leq 1000$，$0 < g \leq \sum_{i=1}^{g} f_i \leq 2000$。 部分测试点的特殊性质详见下表，比如测试点 $1、2$ 中最大应用编号仅为 $10$ 且不包含任何需求。 （表之后再改 tuack 格式）