CF843B Interactive LowerBound

本题为交互题。 给定一个按升序排序的单链表。你需要找到链表中大于等于 $x$ 的最小整数。 更正式地说，链表基于包含 $n$ 个元素的数组构建。第 $i$ 个元素包含两个整数：$value_{i}$ 表示该节点的整数值，$next_{i}$ 表示下一个节点的下标（如果当前节点为链表尾节点，则 $next_{i} = -1$）。链表是有序的，也就是说如果 $next_{i}\neq -1$，则 $value_{next_{i}} > value_{i}$。 你会得到链表中元素个数 $n$，第一个元素的下标 $start$，和整数 $x$。 你最多可以进行 $2000$ 次如下两种类型的查询： - ? i （$1 \leq i \leq n$）—— 查询第 $i$ 个元素的 $value_{i}$ 和 $next_{i}$； - ! ans —— 输出问题的答案：链表中大于等于 $x$ 的最小整数，或者如果没有这样的整数，输出 ! -1。此语句后你的程序应终止。 请编写一个程序解决这个问题。

第一行包含三个整数 $n$、$start$、$x$（$1\leq n \leq 50000$，$1\leq start \leq n$，$0 \leq x \leq 10^9$）——链表中元素数量、首节点下标和整数 $x$。

为输出问题答案，请输出 ! ans，其中 ans 是链表中大于等于 $x$ 的最小整数，若不存在这样的整数则输出 -1。

在每次 ? i 查询后，你将读入两个整数 $value_{i}$ 和 $next_{i}$（$0 \leq value_{i} \leq 10^9$，$-1 \leq next_{i} \leq n$，$next_{i} \ne 0$）。 保证如果 $next_{i} \ne -1$，则 $value_{next_{i}} > value_{i}$。并且数组中的信息组成一个有效的单链表，$start$ 是第一个节点。 注意你不可以进行超过 $1999$ 次 ? 查询。 如果 $next_{i} = -1$ 且 $value_{i} = -1$，说明你查询次数已超上限，或者发起了非法查询。你的程序应立即终止（例如调用 exit(0)）。你会收到 “Wrong Answer” 判定，表示你查询次数超限或查询非法。如果忽略此情况继续读取输入流，可能还会收到其它报错。 如果程序没有任何输出，或者忘记 flush 输出（包括最终答案），你会获得 “Idleness Limit Exceeded” 的判定。 你可以在每次输出查询语句并换行后，使用如下代码刷新缓冲区： - C++ 使用 fflush(stdout)； - Java 使用 System.out.flush()； - Python 使用 stdout.flush()； - Pascal 使用 flush(output)； - 其它语言请参考相关文档。 Hack用例格式： 第一行输出三个整数 $n$、$start$、$x$（$1\leq n\leq 50000$，$1\leq start\leq n$，$0 \leq x \leq 10^9$）。 接下来 $n$ 行，每行两个整数 $value_{i}$ 和 $next_{i}$（$0 \leq value_{i} \leq 10^9$，$-1 \leq next_{i} \leq n$，$next_{i} \ne 0$）。 所输出结构需为有效单链表，特别地，从 $start$ 起应能访问所有节点，并且最后一个节点 $end$ 的 $next_{end}$ 应为 -1。 # 提示 你可以通过如下链接了解更多单链表内容：[https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list](https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list) 下图为第一个样例的说明，起始元素和结束元素用深色标记。 由 ChatGPT 5 翻译