3650 - 【LQ】评测机模拟器

题目描述

题目背景

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

题目描述

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

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

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

「累积评测时间」定义:假设对于某个评测节点,其被分配了 a1, a2, ..., ak 共 k 个任务。那么这个评测节点的「累积评测时间」就是 ta1 + ta2 +... + tak。显然的,如果某个评测节点从未被分配过这 m 个任务中的任何一个,那么这个评测节点的「累积评测时间」是 0。

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

输入

第一行为两个整数 n, m,代表评测节点数量和评测任务数量。
第二行为 m 个整数 t1, t2, ..., tm,依次代表这 m 个评测任务的所需时间。

输出

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

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

样例

输入

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% 的数据,保证 1 <= n, m <= 5 * 10 ^ 3,0 <= ti <= 10 ^ 9。

测试点编号n <=m <=特殊性质
1 ~21010
3 ~ 45 10 ^ 3 | 5 10 ^ 3ti = 0
5 ~ 65 10 ^ 3 | 5 10 ^ 3ti = 1
7 ~ 105 10 ^ 3 | 5 10 ^ 3
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过人数 1
金币数量 2 枚
难度 基础


上一题 下一题