AT_stpc2025_2_n Fair Flags

有 $N$ 个人站在数轴上，第 $i$ 个人在坐标 $A_i$ 处。同时给定正整数 $L, R \ (L \le R)$。 现在考虑在数轴上插 $1$ 根或多根旗子。假设插了 $k$ 根旗子，旗子的位置为 $x_1, x_2, \dots, x_k$。当且仅当以下两个条件同时满足时，这种插旗方式称为**良好插旗方式**： - 所有旗子都插在整数坐标上。即对于所有 $j = 1, 2, \dots, k$，有 $x_j$ 为整数。 - 对于每一个人来说，他距离最近的旗子的距离在 $L$ 到 $R$ 之间。也就是说，对于所有 $i = 1, 2, \dots, N$，都有 $L \le \bigl( \min_{1\le j\le k} |A_i - x_j| \bigr) \le R$。 如果存在良好的插旗方式，**请最小化旗子的数量**并给出构造方法；如果不存在，请报告无法构造。已知若存在良好插旗方式，所需旗子的最小数量 $k$ 满足 $k \le 8N$。 请对 $T$ 组测试用例分别给出答案。

输入按以下格式给出。 > $T$ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 其中，$\mathrm{case}_i$ 表示第 $i$ 个测试用例，其格式如下： > $N$ $L$ $R$ $A_1$ $A_2$ $\cdots$ $A_N$

对于每组测试用例，如果存在良好的插旗方式，输出旗子的数目 $k \ (1 \le k \le 8N)$ 以及旗子的坐标 $x_1, x_2, \dots, x_k\ (-10^9 \le x_i \le 10^9)$，格式如下： > $k$ $x_1$ $x_2$ $\cdots$ $x_k$ 如果不存在良好的插旗方式，输出 `-1`。

## 部分分 若满足以下所有条件，可获得部分分 $25$ 分： - 对于不存在良好插旗方式的测试用例，正确报告无法构造。 - 对于存在良好插旗方式的测试用例，给出的插旗方案为良好插旗方式，且旗子数量不超过 $8N$。 - 存在某个测试用例有良好插旗方式，但旗子的数量未最小化。 ## 样例解释 1 第 $1$ 个测试用例中，人站在坐标 $0$，其到最近旗子的距离需在 $3$ 到 $6$ 之间。 输出样例中，把 $1$ 根旗子插在坐标 $6$，此时距离为 $6$，符合条件，实现了旗子数量最小化。同时， ``` 1 -2 ``` 若输出为这样，则距离 $0$ 最近的旗子为 $-2$，距离为 $2$，不满足距离要求，不是良好插旗方式。 # 数据范围 - 输入均为整数 - $1 \le T \le 2 \times 10^4$ - $1 \le N \le 2\times 10^5$ - $1 \le L \le R \le 5 \times 10^8$ - $-5\times 10^8 \le A_1 < A_2 < \dots < A_N \le 5\times 10^8$ - 所有测试用例中 $N$ 的总和不超过 $4 \times 10^5$。 由 ChatGPT 5 翻译