#P9214. [入门赛 #11] 洛谷评测机模拟器 (Hard Version)

[入门赛 #11] 洛谷评测机模拟器 (Hard Version)

题目背景

本题与 Easy Version 题意完全相同,不同的地方在于数据范围。

现在假装你是洛谷评测机。这一天,洛谷同时进行了 PION 自测、SCP 自测、ION 自测等等比赛。成千上万的评测落到了你的身上!

题目描述

现在已经知道你有 nn 个相同性能的评测节点,它们被分别标号为 1,2,,n1, 2, \cdots, n。一个评测节点在同一时间只能处理一个评测任务。

在某一时刻,mm 个评测任务同时涌入了你。我们将这些任务分别标号为 1,2,,m1, 2, \cdots, m。这些评测任务需要的评测时间分别为 t1,t2,,tmt _ 1 , t _ 2, \cdots, t _ m。每个评测任务需要且仅需要一个评测节点来运行,因此你会按照如下方式按照 1m1 \sim m 的顺序依次将这些评测任务分配到评测节点上:

对于某个耗时 tit _ i 的评测任务,你需要找到目前累积评测时间最小的评测节点将任务放入。如果有多个评测节点累积评测时间相同且最小,则找一个标号最小的节点将任务放入。

「累积评测时间」定义:假设对于某个评测节点,其被分配了 a1,a2,,aka _ 1, a _ 2, \cdots, a _ kkk 个任务。那么这个评测节点的「累积评测时间」就是 ta1+ta2++takt _ {a _ 1} + t _ {a _ 2} + \cdots + t _ {a _ k}。显然的,如果某个评测节点从未被分配过这 mm 个任务中的任何一个,那么这个评测节点的「累积评测时间」是 00

现在,你需要统计出,你的这 nn 个评测节点分别接受了哪一些评测任务。

输入格式

输入共两行。

第一行为两个整数 n,mn, m,代表评测节点数量和评测任务数量。
第二行为 mm 个整数 t1,t2,,tmt _ 1, t _ 2, \cdots, t _ m,依次代表这 mm 个评测任务的所需时间。

输出格式

输出共 nn 行,每行若干个整数,两两之间以一个空格隔开。

对于第 ii 行,输出第 ii 个评测节点接受的评测任务编号从小到大排序后的结果。如果第 ii 个评测节点没有被分配任务,那么输出一行一个 00

5 10
13 50 90 38 60 64 60 77 6 24
1 6
2 8
3
4 7
5 9 10
12 7
85 99 82 90 14 11 15
1
2
3
4
5
6
7
0
0
0
0
0

提示

数据规模与约定

对于 100%100\% 的数据,保证 1n,m5×1051 \leq n, m \leq 5 \times 10 ^ 50ti1090 \leq t _ i \leq 10 ^ 9