P13989 [PO Final 2023] 锯木 / The Sawmill

1G, 1s, sagverket

Alma 有很多木板，她想把这些木板锯成若干段。因此，她来到了一家能够自动切割并分类木板的先进锯木厂。每块木板可以表示为一条无限长的 $ x $ 轴，锯木厂会在 $ N+1 $ 个位置 $ x_1, x_2, \dots, x_N, v $ 处切割，其中 $ v $ 是由用户选择的一个数。随后，所有有限长度的木段会被分类并输出。Alma 想知道这些数 $ x_1, x_2, \dots, x_N $，但似乎没有人知道锯木厂内部的结构。于是，她计划通过投入若干选择得当的 $ v $ 来找出这些数。 有 $ N $ 个秘密整数 $ 1 \le x_1 < x_2 < \dots < x_N \le 10^9 $。注意这些数两两不同。你的目标是找出这些数。你可以向锯木厂送入木板。锯木厂以一个整数 $ v $ 作为输入（$ 1 \le v \le 10^9 $），并执行如下操作： 1. 创建列表 $ L = [x_1, x_2, \dots, x_N, v] $。 2. 对 $ L $ 排序。 3. 创建列表 $ D $，其中对所有 $ i = 1, 2, \dots, N $，有 $ D_i = L_{i+1} - L_i $。 4. 对 $ D $ 排序，并返回其中的 $ N $ 个整数。 你最多可以送入 $ N $ 块木板，**但在子任务 $ 4 $ 中可以送入 $ \textcolor{red}{N+1} $ 块木板**。 ### 实现细节 你的程序应首先读入两个整数 $ N $ 和 $ T $（$ 1 \le N \le 1000, 1 \le T \le 5 $）。$ N $ 是需要找出的秘密数字个数，$ T $ 是测试组编号。给出 $ T $ 的原因是为了便于获得部分分。 接着，你可以开始送入木板。打印一行 $\texttt{? }v$ 以向锯木厂送入带有数字 $ v $ 的木板。数 $ v $ 必须满足 $ 1 \le v \le 10^9 $。随后，你的程序应在一行中读入 $ N $ 个整数，即 $ D_1, D_2, \dots, D_N $。注意：如果 $ v $ 恰好等于某个 $ x_i $，则 $ D_1 $ 可能为 $ 0 $。 当你已经找到 $ x_1, x_2, \dots, x_N $ 时，你应打印一行 $\texttt{!}$ $ x_1 $ $ x_2 $ $ x_3 $ $\ldots$ $ x_N $。 然后你的程序应终止，并且不再打印任何内容。 **请在每次询问后都刷新缓冲区**，否则可能会因为超时而被判为超时。在 C++ 中可使用例如 `cout

见「实现细节」。

见「实现细节」。

### 子任务 **本题采用捆绑测试。** | 子任务编号 | 分值 | 限制 | |:-:|:-:|-------------| | $ 1 $ | $ 15 $ | $ N = 1 $ | | $ 2 $ | $ 15 $ | $ N = 2 $ | | $ 3 $ | $ 11 $ | $ x_i \le N + 1 $ | | $ 4 $ | $ 37 $ | $ N \le 100, x_i \le 10^4 $，可最多发送 $ \textcolor{red}{N+1} $ 块木板。 | | $ 5 $ | $ 22 $ | 无额外约束。 |