这个问题与其他两个版本之间的唯一区别是最大查询数。在此版本中,您最多可以提出 $$$\mathbf{25}$$$ 查询。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。
这是一个交互问题。
“大家!多米的完美数据结构课即将开始!如果你想拥有和我一样高的智商,就来加油吧!”今天的数据结构课,Doremy 正在教大家一个强大的数据结构——Doremy 树!现在她给你一个测验来证明你在课堂上专心听讲。
Given an array $$$a$$$ of length $$$m$$$, Doremy tree supports the query $$$Q(l,r,k)$$$, where $$$1 \leq l \leq r \leq m$$$ and $$$1 \leq k \leq m$$$, which returns the number of distinct integers in the array $$$\left[\lfloor\frac{a_l}{k} \rfloor, \lfloor\frac{a_{l+1}}{k} \rfloor, \ldots, \lfloor\frac{a_r}{k} \rfloor\right]$$$。
Doremy 有一个从 $$$1$$$ 到 $$$n$$$ 整数的秘密排列 $$$p$$$。您可以进行查询,在一个查询中,给出 $$$3$$$ 整数 $$$l,r,k$$$ ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq k \leq n$$$) 并接收数组 $$$p$$$ 的 $$$Q(l,r,k)$$$ 值。您能否找到索引 $$$y$$$ ($$$1 \leq y \leq n$$$) 使得 $$$p_y=1$$$ 在最多 $$$\mathbf{25}$$$ 查询中?
请注意,在进行任何查询之前,排列 $$$p$$$ 是固定的。
互动
You begin the interaction by reading an integer $$$n$$$ ($$$3 \le n \le 1024$$$) in the first line — the length of the permutation.
要进行查询,您应该输出
- "? $$$l\ r\ k$$$" ($$$1 \leq l \leq r \leq n$$$, $$$1 \leq k \leq n$$$)
要给出答案,您应该输出
- "!$$$y$$$" ($$$1 \leq y \leq n$$$)
打印查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客格式
破解的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1024$$$) — 排列的长度。
攻击的第二行包含 $$$n$$$ 不同的整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i\le n$$$) — 排列。
示例
输入 #1
5 2 2 1 3
输出 #1
? 1 3 4 ? 3 5 3 ? 3 4 5 ? 3 5 2 ! 4
注意
示例中的排列为 $$$[3,5,2,1,4]$$$。
例如,输入和输出说明了该测试中可能的交互(插入空行只是为了清楚起见)。
在这个交互过程中:
- For the first query, $$$\lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=0$$$, so the answer is $$$2$$$.
- For the second query, $$$\lfloor\frac{2}{3}\rfloor=0,\lfloor\frac{1}{3}\rfloor=0,\lfloor\frac{4}{3}\rfloor=1$$$, so the answer is still $$$2$$$.
- 对于第三个查询,$$$\lfloor\frac{2}{5}\rfloor=0,\lfloor\frac{1}{5}\rfloor=0$$$,因此答案是 $$$1$$$。
- For the fourth query, $$$\lfloor\frac{2}{2}\rfloor=1,\lfloor\frac{1}{2}\rfloor=0,\lfloor\frac{4}{2}\rfloor=2$$$, so the answer is $$$3$$$.
经过$$$4$$$查询后得到正确答案,因此判断此过程正确。