A16497. Snake Instructions
编程题
NOI/NOI+/CTSC
知识点
题目描述
这是一个交互题。
数轴上有 $n$ 条蛇。第 $i$ 条蛇在位置 $a_i$，速度为 $s_i$。你已知每条蛇的位置，并且每条蛇的速度是 $0$ 到 $2$ 的整数，但你不知道具体每条蛇的速度。保证没有两条蛇处于相同的位置。
为了确定所有蛇的速度，你最多可以进行 $3$ 次指令。每条指令应以长度为 $m$ 的二进制字符串给出，字符串只包含 L 和 R （$1 \leq m \leq 4n$）。收到这条指令后，所有蛇会运动 $m$ 秒。在第 $i$ 秒，如果 $s_i=$ L，则所有蛇向左运动一秒，否则全部蛇向右运动一秒。如果在某一时刻（包括非整数秒时），有两条蛇处于相同的位置，则速度快的那条蛇被移除。$m$ 秒后，你会获得剩下的蛇的数量 $k$，以及所有剩余蛇的位置。注意，每次指令都是独立的——也就是说，所有蛇都会复活回到起始位置再开始新的操作。
你的任务是确定所有蛇的速度。然而，可能存在无法确定某一条蛇的速度的情况，如果碰到这种情况，你需要输出 $-1$。只有当无论给出哪一组最多 $3$ 条指令都无法确定某条蛇的速度时，才能输出 $-1$。如果存在至多 $3$ 条指令能唯一确定所有蛇的速度而你输出了 $-1$，你会得到 Wrong Answer 判决。同理，如果本应该输出 $-1$ 却没有输出也会判错，即使你“猜”对了速度。
数轴上有 $n$ 条蛇。第 $i$ 条蛇在位置 $a_i$，速度为 $s_i$。你已知每条蛇的位置，并且每条蛇的速度是 $0$ 到 $2$ 的整数，但你不知道具体每条蛇的速度。保证没有两条蛇处于相同的位置。
为了确定所有蛇的速度，你最多可以进行 $3$ 次指令。每条指令应以长度为 $m$ 的二进制字符串给出，字符串只包含 L 和 R （$1 \leq m \leq 4n$）。收到这条指令后，所有蛇会运动 $m$ 秒。在第 $i$ 秒，如果 $s_i=$ L，则所有蛇向左运动一秒，否则全部蛇向右运动一秒。如果在某一时刻（包括非整数秒时），有两条蛇处于相同的位置，则速度快的那条蛇被移除。$m$ 秒后，你会获得剩下的蛇的数量 $k$，以及所有剩余蛇的位置。注意，每次指令都是独立的——也就是说，所有蛇都会复活回到起始位置再开始新的操作。
你的任务是确定所有蛇的速度。然而，可能存在无法确定某一条蛇的速度的情况，如果碰到这种情况，你需要输出 $-1$。只有当无论给出哪一组最多 $3$ 条指令都无法确定某条蛇的速度时，才能输出 $-1$。如果存在至多 $3$ 条指令能唯一确定所有蛇的速度而你输出了 $-1$，你会得到 Wrong Answer 判决。同理，如果本应该输出 $-1$ 却没有输出也会判错，即使你“猜”对了速度。
输入格式
每个测试包含多个测试用例。第一行为用例数量 $t$（$1 \le t \le 10^3$），随后是所有用例的描述。
每个用例的第一行为整数 $n$，即蛇的数量（$2 \leq n \leq 10^5$）。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_1<a_2<\ldots<a_n \leq 4n$），表示所有蛇的初始位置。
保证所有用例的 $n$ 之和不超过 $10^5$。
每个用例的第一行为整数 $n$，即蛇的数量（$2 \leq n \leq 10^5$）。
第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_1<a_2<\ldots<a_n \leq 4n$），表示所有蛇的初始位置。
保证所有用例的 $n$ 之和不超过 $10^5$。
输出格式
**交互说明**
读入所有蛇的位置后，开始交互。每次发出指令需按以下格式输出一行：
-
你需保证 $s$ 只由字母
评测器会返回如下格式的一行：
- $k\ b_1\ b_2\ \ldots\ b_k$（$1 \leq k \leq n, -10^9 \leq b_1<b_2<\ldots<b_k \leq 10^9$）
其中 $k$ 表示指令后剩余蛇的数量，$b_1,b_2,\ldots,b_k$ 为它们的最终位置。
当你准备好输出答案时，输出一行：
- 如果无法确定所有蛇的速度，输出
- 否则，输出
输出答案不计入指令次数。
之后继续下一个用例或程序最后终止。
交互器**不自适应**，即所有蛇的速度在整个过程都保持不变，并保证输入合法——即所有信息与各自速度兼容。
每次输出查询后请务必换行并刷新输出缓冲，否则会收到 Idleness limit exceeded 的判决。
若某一步收到 $-1$，表示你有非法查询或其他错误，应立即退出，否则程序继续读取已关闭流会导致不可预期的判决。
**Hack 格式**
自定义 hack 时，输入如下格式：
第一行为整数 $t$，即用例数（$1 \leq t \leq 10^3$）。
每个用例的第一行为 $n$（$2 \leq n \leq 10^5$）。
第二行为 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_1<a_2<\ldots<a_n \leq 4n$）。
第三行为 $n$ 个整数 $s_1,s_2,\ldots,s_n$（$0 \leq s_i \leq 2$），表示每条蛇的速度。
所有用例的 $n$ 之和不超过 $10^5$。
要刷新输出缓冲：
- C++：fflush(stdout) 或 cout.flush()；
- Python：sys.stdout.flush()；
- 其它语言请查阅相关文档。
读入所有蛇的位置后，开始交互。每次发出指令需按以下格式输出一行：
-
? s你需保证 $s$ 只由字母
L 和 R 组成，且长度在 $1$ 到 $4n$ 之间。评测器会返回如下格式的一行：
- $k\ b_1\ b_2\ \ldots\ b_k$（$1 \leq k \leq n, -10^9 \leq b_1<b_2<\ldots<b_k \leq 10^9$）
其中 $k$ 表示指令后剩余蛇的数量，$b_1,b_2,\ldots,b_k$ 为它们的最终位置。
当你准备好输出答案时，输出一行：
- 如果无法确定所有蛇的速度，输出
! -1- 否则，输出
! s_1 s_2 \ldots s_n（$0 \leq s_i \leq 2$），其中 $s_i$ 表示第 $i$ 条蛇的速度。输出答案不计入指令次数。
之后继续下一个用例或程序最后终止。
交互器**不自适应**，即所有蛇的速度在整个过程都保持不变，并保证输入合法——即所有信息与各自速度兼容。
每次输出查询后请务必换行并刷新输出缓冲，否则会收到 Idleness limit exceeded 的判决。
若某一步收到 $-1$，表示你有非法查询或其他错误，应立即退出，否则程序继续读取已关闭流会导致不可预期的判决。
**Hack 格式**
自定义 hack 时，输入如下格式：
第一行为整数 $t$，即用例数（$1 \leq t \leq 10^3$）。
每个用例的第一行为 $n$（$2 \leq n \leq 10^5$）。
第二行为 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_1<a_2<\ldots<a_n \leq 4n$）。
第三行为 $n$ 个整数 $s_1,s_2,\ldots,s_n$（$0 \leq s_i \leq 2$），表示每条蛇的速度。
所有用例的 $n$ 之和不超过 $10^5$。
要刷新输出缓冲：
- C++：fflush(stdout) 或 cout.flush()；
- Python：sys.stdout.flush()；
- 其它语言请查阅相关文档。
输入输出样例
输入 #1
7 2 1 2 1 1 2 1 6 2 1 4 3 2 3 4 2 2 4 3 2 3 4 3 5 6 7 5 1 3 8 14 15 5 1 2 3 4 5 4 5 6 7 8
输出 #1
? L ! 0 1 ? LRLL ! 0 1 ? RRR ! -1 ? RRR ! 1 1 1 ! 2 1 0 0 1 ! 0 2 2 2 0 ! 0 1 2 0
说明/提示
在第一个用例中，两条蛇速度分别为 $0$ 和 $1$。程序首先给出指令 L。右边那条蛇从 $2$ 移动到 $1$，而左边的蛇不动。此时两条蛇都在 $1$，速度较大的蛇（右边那只）被移除。因此只剩下一条蛇在位置 $1$。此时程序猜测两条蛇的速度分别为 $0$ 和 $1$，这是正确的。注意，尽管速度 $[0,2]$ 也会导致最后只剩一只蛇在 $1$，但不能直接输出 $-1$，因为还可以通过另一组指令区分 $[0,2]$ 和 $[0,1]$。
在第三个用例中，可以确定第一条蛇和第三条蛇的速度均为 $0$，且可以证明无论如何无法区分中间那条蛇的速度是 $1$ 还是 $2$，因此输出 $-1$ 是正确的。
在第三个用例中，可以确定第一条蛇和第三条蛇的速度均为 $0$，且可以证明无论如何无法区分中间那条蛇的速度是 $1$ 还是 $2$，因此输出 $-1$ 是正确的。