AT_xmascon25_g Gon Pack

设 $N$ 为正整数。 令集合 $\{1, 2, \ldots, 2N\}$ 的所有划分成 $N$ 元集合的 $2$ 个子集的划分全集为 $\mathcal{P}$。有 $|\mathcal{P}| = \frac{1}{2} \binom{2N}{N}$。例如，当 $N = 3$ 时，$\{\{ 1, 5, 6 \}, \{ 2, 3, 4 \}\} \in \mathcal{P}$。 对于满足 $1 \le a_1 < a_2 < \cdots < a_{2N}$ 的整数序列 $(a_1, a_2, \ldots, a_{2N})$，**好划分**定义为：$P \in \mathcal{P}$，且对任意 $I \in P$，存在一个边长集合为 $\{ a_i \mid i \in I \}$ 的非退化简单 $N$ 边形。例如，当 $N = 3$ 时，$\{\{ 1, 5, 6 \}, \{ 2, 3, 4 \}\}$ 为好划分的条件是 $a_1, a_5, a_6$ 能作为三角形的三边，且 $a_2, a_3, a_4$ 也能作为三角形的三边。 给定 $N$ 和一个 $P \in \mathcal{P}$。问是否存在仅当 $P$ 是好划分时才成立的整数序列 $1 \le a_1 < a_2 < \cdots < a_{2N}$？ - 如果存在，则可以证明一定存在 $a_{2N} \le 10^{17}$ 的满足条件的 $(a_1, a_2, \ldots, a_{2N})$。请给出一个满足所有条件的 $(a_1, a_2, \ldots, a_{2N})$。 - 如果不存在，则存在满足下列条件的非负整数 $k$ 和划分 $Q_1, Q_2, \ldots, Q_k \in \mathcal{P}$，请输出其中使得 $k$ 最小的一组解： - 对于 $j = 1, 2, \ldots, k$，都有 $Q_j \ne P$。 - 对任意 $1 \le a_1 < a_2 < \cdots < a_{2N}$，若 $P$ 是好划分，则 $Q_1, Q_2, \ldots, Q_k$ 至少有一个也是好划分。 在输入输出中，$\mathcal{P}$ 的每个元素用由 $N$ 个 `0` 和 $N$ 个 `1` 组成的**以 `1` 结尾**的字符串表示。每个字符种类索引的集合代表划分的每个子集。例如，当 $N=3$ 时，$\{\{ 1, 5, 6 \}, \{ 2, 3, 4 \}\}$ 用 `100011` 表示。

输入从标准输入读入，格式如下： > $N$ $P$

根据问题的两种情况，输出以下格式之一： > YES $a_1$ $a_2$ $\cdots$ $a_{2N}$ > NO $k$ $Q_1$ $Q_2$ $\cdots$ $Q_k$

## 部分分 - 满足限制的所有输入数据各包含一种。每个数据点正确可得 $N$ 分。 ## 样例解释 1 $P = \{\{ 1, 5, 6 \}, \{ 2, 3, 4 \}\}$。 在此输出样例中，$2, 10, 11$ 可以作为三角形的三边，$4, 6, 8$ 也可作为三角形的三边，因此 $P$ 是好划分。可以证明其他划分均不是好划分。 ## 样例解释 2 $P = \{\{ 1, 4, 6 \}, \{ 2, 3, 5 \}\}$。 如果满足如下 $3$ 个条件： - $1 \le a_1 < a_2 < a_3 < a_4 < a_5 < a_6$ - $a_1, a_4, a_6$ 可以作为三角形三边 - $a_2, a_3, a_5$ 可以作为三角形三边 那么下述 $2$ 个条件必然也满足： - $a_1, a_5, a_6$ 可以作为三角形三边 - $a_2, a_3, a_4$ 可以作为三角形三边 # 数据范围 - $3 \le N \le 5$。 由 ChatGPT 5 翻译