CF1697F Too Many Constraints

你需要构造一个由 $n$ 个整数组成的数组 $a$，其中每个元素都在 $1$ 到 $k$ 之间。 该数组必须是非递减的（即对于所有 $i$ 满足 $1 \le i \le n-1$，都有 $a_i \le a_{i+1}$）。 你还会得到一些额外的限制条件。每个限制条件属于以下三种类型之一： - $1~i~x$：$a_i$ 不能等于 $x$； - $2~i~j~x$：$a_i + a_j$ 必须小于等于 $x$； - $3~i~j~x$：$a_i + a_j$ 必须大于等于 $x$。 请构造任意一个满足所有限制条件的非递减数组，或者报告不存在这样的数组。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n, m, k$（$2 \le n \le 2 \cdot 10^4$；$0 \le m \le 2 \cdot 10^4$；$2 \le k \le 10$）。 接下来的 $m$ 行，每行描述一个限制条件，格式如下： - $1~i~x$（$1 \le i \le n$；$1 \le x \le k$）：$a_i$ 不能等于 $x$； - $2~i~j~x$（$1 \le i < j \le n$；$2 \le x \le 2 \cdot k$）：$a_i + a_j$ 必须小于等于 $x$； - $3~i~j~x$（$1 \le i < j \le n$；$2 \le x \le 2 \cdot k$）：$a_i + a_j$ 必须大于等于 $x$。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^4$。所有测试用例中 $m$ 的总和也不超过 $2 \cdot 10^4$。

对于每个测试用例，判断是否存在满足所有条件的非递减数组。如果不存在，输出 $-1$。否则，输出任意一个合法的数组——$n$ 个从 $1$ 到 $k$ 的整数。

由 ChatGPT 4.1 翻译