CF978G Petya's Exams

Petya 在大学学习。本学年以 $n$ 个特殊日子结束。Petya 需要在这些特殊日子里通过 $m$ 门考试。这些特殊日子从 $1$ 到 $n$ 编号。 每门考试有三个参数： - $s_i$ —— 第 $i$ 门考试的试题公布的日子， - $d_i$ —— 第 $i$ 门考试的考试日（$s_i < d_i$）， - $c_i$ —— Petya 需要为第 $i$ 门考试准备的天数。对于第 $i$ 门考试，Petya 应该在 $s_i$ 到 $d_i-1$ 之间的日子（包含两端）进行准备。 每天，Petya 有三种活动可以选择：什么都不做（休息）、参加一门考试，或为一门考试准备。因此，他一天不能准备/参加多门考试，也不能混合活动。如果他在第 $j$ 天为第 $i$ 门考试做准备，则 $s_i \le j < d_i$。 允许在准备某门考试时中断，也可以在连续的几天内交替为不同的考试做准备。因此，准备某门考试不要求连续进行。 请为 Petya 安排一个能够准备并通过所有考试的日程表，或者报告无法完成。

第一行包含两个整数 $n$ 和 $m$，$2 \le n \le 100, 1 \le m \le n$，分别表示天数和考试数。 接下来的 $m$ 行，每行包含三个整数 $s_i, d_i, c_i$，$1 \le s_i < d_i \le n, 1 \le c_i \le n$，分别表示第 $i$ 门考试的试题公布日、考试日和需要准备的天数。 保证所有考试的考试日都不同。不同考试的试题可以在同一天公布。某一天既可能是某场考试的考试日，也可能是另一场考试的试题公布日。

如果 Petya 无法准备并通过所有考试，输出 $-1$。如果可以，输出 $n$ 个整数，第 $j$ 个数表示： - 如果第 $j$ 天是某场考试的考试日，输出 $m+1$（每一天最多只进行一场考试）； - 如果第 $j$ 天 Petya 休息，输出 $0$； - 如果第 $j$ 天 Petya 为第 $i$ 门考试做准备，输出 $i$（$1 \le i \le m$，且每门考试的准备天数严格等于所需天数）。假设考试编号按输入顺序，从 $1$ 开始。 如果有多种可行的日程安排，输出任意一种。

在第一个样例中，Petya 可以在第一天为第 $1$ 门考试准备，在第二天为第 $2$ 门考试准备，在第三天参加第 $1$ 门考试，第四天休息，第五天参加第 $2$ 门考试。因此，他可以准备并通过所有考试。 在第二个样例中，有三天和两场考试。因此，Petya 只能有一天用于准备（因为另外两天要参加考试）。所以 Petya 无法准备并通过所有考试。 由 ChatGPT 4.1 翻译