309553: CF1697F. Too Many Constraints
Memory Limit：512 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Too Many Constraints
题意翻译
构造一个长度为 $n$ 的数列 $a$，其中 $1\le a_i\le k$ 且 $a$ 不降，即对于所有 $1\le i \le n-1$，$a_i \le a_{i+1}$。给出 $m$ 个约束，有三种约束，其中： $1\;i\;x$，表示 $a_i \neq x$ $2\;i\;j\;x$，表示 $a_i+ a_j\le x$ $3\;i\;j\;x$，表示 $a_i+ a_j\ge x$ 现在有 $t$ 组数据，要求你给出这个数列。无解输出 $-1$。题目描述
You are asked to build an array $ a $ , consisting of $ n $ integers, each element should be from $ 1 $ to $ k $ . The array should be non-decreasing ( $ a_i \le a_{i+1} $ for all $ i $ from $ 1 $ to $ n-1 $ ). You are also given additional constraints on it. Each constraint is of one of three following types: - $ 1~i~x $ : $ a_i $ should not be equal to $ x $ ; - $ 2~i~j~x $ : $ a_i + a_j $ should be less than or equal to $ x $ ; - $ 3~i~j~x $ : $ a_i + a_j $ should be greater than or equal to $ x $ . Build any non-decreasing array that satisfies all constraints or report that no such array exists.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains three integers $ n, m $ and $ k $ ( $ 2 \le n \le 2 \cdot 10^4 $ ; $ 0 \le m \le 2 \cdot 10^4 $ ; $ 2 \le k \le 10 $ ). The $ i $ -th of the next $ m $ lines contains a description of a constraint. Each constraint is of one of three following types: - $ 1~i~x $ ( $ 1 \le i \le n $ ; $ 1 \le x \le k $ ): $ a_i $ should not be equal to $ x $ ; - $ 2~i~j~x $ ( $ 1 \le i < j \le n $ ; $ 2 \le x \le 2 \cdot k $ ): $ a_i + a_j $ should be less than or equal to $ x $ ; - $ 3~i~j~x $ ( $ 1 \le i < j \le n $ ; $ 2 \le x \le 2 \cdot k $ ): $ a_i + a_j $ should be greater than or equal to $ x $ . The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ . The sum of $ m $ over all testcases doesn't exceed $ 2 \cdot 10^4 $ .
输出格式
For each testcase, determine if there exists a non-decreasing array that satisfies all conditions. If there is no such array, then print -1. Otherwise, print any valid array — $ n $ integers from $ 1 $ to $ k $ .
输入输出样例
输入样例 #1
4
4 0 4
2 2 3
3 1 2 3
1 2 2
3 3 2
1 1 1
2 2 3 2
3 2 3 2
5 5 5
3 2 5 7
2 4 5 10
3 4 5 6
3 3 4 7
2 1 5 7输出样例 #1
1 2 3 4
1 3
-1
1 2 2 5 5Input
题意翻译
构造一个长度为 $n$ 的数列 $a$，其中 $1\le a_i\le k$ 且 $a$ 不降，即对于所有 $1\le i \le n-1$，$a_i \le a_{i+1}$。给出 $m$ 个约束，有三种约束，其中： $1\;i\;x$，表示 $a_i \neq x$ $2\;i\;j\;x$，表示 $a_i+ a_j\le x$ $3\;i\;j\;x$，表示 $a_i+ a_j\ge x$ 现在有 $t$ 组数据，要求你给出这个数列。无解输出 $-1$。Output
题目大意：
构造一个长度为 $n$ 的数列 $a$，其中 $1\le a_i\le k$ 且 $a$ 不降，即对于所有 $1\le i \le n-1$，$a_i \le a_{i+1}$。给出 $m$ 个约束，有三种约束，其中：
1. $1\;i\;x$，表示 $a_i \neq x$
2. $2\;i\;j\;x$，表示 $a_i+ a_j\le x$
3. $3\;i\;j\;x$，表示 $a_i+ a_j\ge x$
现在有 $t$ 组数据，要求你给出这个数列。无解输出 $-1$。
输入输出数据格式：
输入格式：
- 第一行包含一个整数 $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$ 行中的第 $i$ 行包含一个约束的描述。每个约束是以下三种类型之一：
- $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$ 的整数。题目大意： 构造一个长度为 $n$ 的数列 $a$，其中 $1\le a_i\le k$ 且 $a$ 不降，即对于所有 $1\le i \le n-1$，$a_i \le a_{i+1}$。给出 $m$ 个约束，有三种约束，其中： 1. $1\;i\;x$，表示 $a_i \neq x$ 2. $2\;i\;j\;x$，表示 $a_i+ a_j\le x$ 3. $3\;i\;j\;x$，表示 $a_i+ a_j\ge x$ 现在有 $t$ 组数据，要求你给出这个数列。无解输出 $-1$。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $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$ 行中的第 $i$ 行包含一个约束的描述。每个约束是以下三种类型之一： - $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$ 的整数。
构造一个长度为 $n$ 的数列 $a$，其中 $1\le a_i\le k$ 且 $a$ 不降，即对于所有 $1\le i \le n-1$，$a_i \le a_{i+1}$。给出 $m$ 个约束，有三种约束，其中：
1. $1\;i\;x$，表示 $a_i \neq x$
2. $2\;i\;j\;x$，表示 $a_i+ a_j\le x$
3. $3\;i\;j\;x$，表示 $a_i+ a_j\ge x$
现在有 $t$ 组数据，要求你给出这个数列。无解输出 $-1$。
输入输出数据格式：
输入格式：
- 第一行包含一个整数 $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$ 行中的第 $i$ 行包含一个约束的描述。每个约束是以下三种类型之一：
- $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$ 的整数。题目大意： 构造一个长度为 $n$ 的数列 $a$，其中 $1\le a_i\le k$ 且 $a$ 不降，即对于所有 $1\le i \le n-1$，$a_i \le a_{i+1}$。给出 $m$ 个约束，有三种约束，其中： 1. $1\;i\;x$，表示 $a_i \neq x$ 2. $2\;i\;j\;x$，表示 $a_i+ a_j\le x$ 3. $3\;i\;j\;x$，表示 $a_i+ a_j\ge x$ 现在有 $t$ 组数据，要求你给出这个数列。无解输出 $-1$。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $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$ 行中的第 $i$ 行包含一个约束的描述。每个约束是以下三种类型之一： - $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$ 的整数。