CF1840G2 In Search of Truth (Hard Version)

本题的简单版与困难版的唯一区别在于最多允许的查询次数。在本题中，你最多可以进行 $1000$ 次查询。 这是一个交互题。 你正在玩一个游戏。一个圆被分成了 $n$ 个扇区，扇区按照某种顺序编号为 $1$ 到 $n$。你在隔壁房间，并不知道扇区的数量 $n$ 以及各个扇区的编号。圆上有一个指针，最初指向某个扇区。起初，主持人会告诉你指针当前所指的扇区编号。之后，你可以最多 $1000$ 次请求主持人将指针顺时针或逆时针移动 $k$ 个扇区。每次移动后，主持人会告诉你指针当前所指的扇区编号。 你的任务是在最多 $1000$ 次查询内，确定整数 $n$——即扇区的总数。 保证 $1 \le n \le 10^6$。

输入包含一个整数 $x$（$1 \le x \le n$），表示指针初始所指的扇区编号。

当你确定了整数 $n$（扇区总数）后，应输出 "! n"（$1 \le n \le 10^6$）。输出后程序应立即终止。 注意，输出答案不计入查询次数。 保证整数 $n$ 以及各个扇区的编号在交互过程中始终固定，不会因你的查询而改变。 交互说明 读入输入描述后，你可以进行如下两种类型的查询： 1. "+ k"（$0 \le k \le 10^9$）——请求将指针顺时针移动 $k$ 个扇区。 2. "- k"（$0 \le k \le 10^9$）——请求将指针逆时针移动 $k$ 个扇区。 每次查询后，你都应读入一个整数 $x$（$1 \le x \le n$），表示当前指针所指的扇区编号。 你最多可以进行 $1000$ 次查询。 如果查询次数过多，将会得到 Wrong answer。 每次输出查询或答案后，别忘了输出换行并刷新输出缓冲区，否则会得到 Idleness limit exceeded。具体操作如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。

Hack 格式 进行 Hack 时，使用如下格式： 第一行输出一个整数 $n$（$1 \le n \le 10^6$），表示扇区总数。 第二行输出 $n$ 个互不相同的整数 $1 \le a_1, a_2, \dots, a_n \le n$，表示顺时针方向上各扇区的编号，指针初始指向编号为 $a_1$ 的扇区。 由 ChatGPT 4.1 翻译