← 返回题目列表

AtCoder · stpc2025_2_n

N. 公平旗帜

中文机器翻译题面 查看原题

配点 : 100 点

問題文

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 。

如果有好的方法可以举旗尽量减少举起旗帜的数量并构建它并报告它(如果不存在)。另外,如果有好的设置flag的方法的话,最少应该设置的flag数量是 k 是 在 8N 可以证明: 请回答

T 测试用例。

制約

  • 所有输入均为整数
  • 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 \lt A_2 \lt \dots \lt A_N \le 5\times 10^8
  • 整个测试用例 N 的总和是 4 \times 10^5 以下

部分点

如果满足以下所有条件,则部分点 25 点。 如果您正确回答了所有满足

  • 据报道,没有良好标志的测试用例是不可能构建的。
  • 据报道,可以构造一个具有良好升旗方式的测试用例,并且构造出的升旗方式为良好升旗方式,升旗次数为 8N 不到1本书。
  • 在其中一个测试用例中,有一种很好的标志放置方法,但标志的数量并未最小化。

入力

输入按以下格式给出。

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 。 在第


入力例 1

4
1 3 6
0
2 5 5
-15 -5
2 3 4
0 2
3 100 100
-100 0 100

出力例 1

1
6 
1
-10 
2
-3 6 
-1

1 个测试用例中,坐标 0 处有人,坐标 从 0 到最近标志的距离是 3 以上 6 。

在示例输出中,1 坐标书标志 它位于 6 ,坐标 最接近 0 的标志(坐标 6) 是到 6 ,所以这是一个很好的升旗方式,而且升旗的数量也被最小化。另一方面, 对于输出

1
-2

,坐标 0 的标志(坐标 -2) 是到 2 和3 以上 6 这不是举旗的好方法,因为它不在下面。 我决定将