309955: CF1764G2. Doremy's Perfect DS Class (Medium Version)
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Doremy's Perfect DS Class (Medium Version)
题意翻译
- **这是一道交互题。** - 交互库有一个 $[1,n]$ 的排列 $p$。 - 你可以询问 $l,r,k$，交互库会返回 $\left\lfloor\dfrac{p_l}k\right\rfloor,\left\lfloor\dfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\dfrac{p_r}k\right\rfloor$ 中不同数的个数。 - 你需要在 $25$ 次询问内找到 $p$ 中 $1$ 的位置。 - $n\in[3,1024]$。题目描述
The only difference between this problem and the other two versions is the maximum number of queries. In this version, you are allowed to ask at most $ \mathbf{25} $ queries. You can make hacks only if all versions of the problem are solved. This is an interactive problem. "Everybody! Doremy's Perfect Data Structure Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's Data Structure class, Doremy is teaching everyone a powerful data structure — Doremy tree! Now she gives you a quiz to prove that you are paying attention in class. 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 has a secret permutation $ p $ of integers from $ 1 $ to $ n $ . You can make queries, in one query, you give $ 3 $ integers $ l,r,k $ ( $ 1 \leq l \leq r \leq n $ , $ 1 \leq k \leq n $ ) and receive the value of $ Q(l,r,k) $ for the array $ p $ . Can you find the index $ y $ ( $ 1 \leq y \leq n $ ) such that $ p_y=1 $ in at most $ \mathbf{25} $ queries? Note that the permutation $ p $ is fixed before any queries are made.输入输出格式
输入格式
输出格式
You begin the interaction by reading an integer $ n $ ( $ 3 \le n \le 1024 $ ) in the first line — the length of the permutation. To make a query, you should output - "? $ l\ r\ k $ " ( $ 1 \leq l \leq r \leq n $ , $ 1 \leq k \leq n $ ) in a separate line. After each query, you should read an integer $ x $ — the value of $ Q(l,r,k) $ for $ p $ . In this version of the problem, you can make at most $ 25 $ such queries.To give the answer, you should output - "! $ y $ " ( $ 1 \leq y \leq n $ ) in a separate line, where $ p_y=1 $ .After printing a query or the answer, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. Hacks Format The first line of the hack contains an integer $ n $ ( $ 3 \le n \le 1024 $ ) — the length of the permutation. The second line of the hack contains $ n $ distinct integers $ p_1,p_2,\ldots,p_n $ ( $ 1 \le p_i\le n $ ) — the permutation.
输入输出样例
输入样例 #1
5
2
2
1
3输出样例 #1
? 1 3 4
? 3 5 3
? 3 4 5
? 3 5 2
! 4说明
The permutation in the example is $ [3,5,2,1,4] $ . The input and output for example illustrate possible interaction on that test (empty lines are inserted only for clarity). In this interaction process: - 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 $ . - For the third query, $ \lfloor\frac{2}{5}\rfloor=0,\lfloor\frac{1}{5}\rfloor=0 $ , so the answer is $ 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 $ . The correct answer is got after $ 4 $ queries, so this process will be judged correct.Input
题意翻译
- **这是一道交互题。** - 交互库有一个 $[1,n]$ 的排列 $p$。 - 你可以询问 $l,r,k$，交互库会返回 $\left\lfloor\dfrac{p_l}k\right\rfloor,\left\lfloor\dfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\dfrac{p_r}k\right\rfloor$ 中不同数的个数。 - 你需要在 $25$ 次询问内找到 $p$ 中 $1$ 的位置。 - $n\in[3,1024]$。Output
**题意翻译**
- **这是一道交互题。**
- 交互库有一个 $[1,n]$ 的排列 $p$。
- 你可以询问 $l,r,k$，交互库会返回 $\left\lfloor\dfrac{p_l}k\right\rfloor,\left\lfloor\dfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\dfrac{p_r}k\right\rfloor$ 中不同数的个数。
- 你需要在 $25$ 次询问内找到 $p$ 中 $1$ 的位置。
- $n\in[3,1024]$。
**题目描述**
这个题目与其他两个版本的区别仅在于查询的最大次数。在这个版本中，你最多可以进行 $ \mathbf{25} $ 次查询。只有当所有版本的问题都解决后，你才能进行 hack。
这是一个交互问题。
“大家注意！Doremy 的完美数据结构课就要开始了！如果你想和我一样聪明，那就加油吧！” 在今天的 数据结构课 上，Doremy 教给大家一个强大的数据结构——Doremy 树！现在她给你一个测验，以证明你在认真听课。
给定一个长度为 $ m $ 的数组 $ a $，Doremy 树支持查询 $ Q(l,r,k) $，其中 $ 1 \leq l \leq r \leq m $ 和 $ 1 \leq k \leq m $，返回数组 $ \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 $。你可以进行查询，在每次查询中，你给出三个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并收到 $ p $ 数组的 $ Q(l,r,k) $ 的值。你能否在最多 $ \mathbf{25} $ 次查询内找到索引 $ y $（$ 1 \leq y \leq n $），使得 $ p_y=1 $？
注意，排列 $ p $ 在进行任何查询之前就已固定。
**输入输出格式**
**输入格式**
你首先在第一行读取一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。
**输出格式**
为了进行查询，你应该输出：
- "? $ l\ r\ k $"（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $）
在单独的一行中。每次查询后，你应该读取一个整数 $ x $——$ p $ 的 $ Q(l,r,k) $ 的值。在这个问题的版本中，你最多可以进行 $ 25 $ 次这样的查询。为了给出答案，你应该输出：
- "! $ y $"（$ 1 \leq y \leq n $）
在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，别忘了输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用：
- 在 C++ 中使用 fflush(stdout) 或 cout.flush()；
- 在 Java 中使用 System.out.flush()；
- 在 Pascal 中使用 flush(output)；
- 在 Python 中使用 stdout.flush()；
- 查看其他语言的文档。
**Hacks 格式**
Hack 的第一行包含一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。
Hack 的第二行包含 $ 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] $。
输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。
在这个交互过程中：
- 对于第一个查询，$\lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rf**题意翻译** - **这是一道交互题。** - 交互库有一个 $[1,n]$ 的排列 $p$。 - 你可以询问 $l,r,k$，交互库会返回 $\left\lfloor\dfrac{p_l}k\right\rfloor,\left\lfloor\dfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\dfrac{p_r}k\right\rfloor$ 中不同数的个数。 - 你需要在 $25$ 次询问内找到 $p$ 中 $1$ 的位置。 - $n\in[3,1024]$。 **题目描述** 这个题目与其他两个版本的区别仅在于查询的最大次数。在这个版本中，你最多可以进行 $ \mathbf{25} $ 次查询。只有当所有版本的问题都解决后，你才能进行 hack。 这是一个交互问题。 “大家注意！Doremy 的完美数据结构课就要开始了！如果你想和我一样聪明，那就加油吧！” 在今天的 数据结构课 上，Doremy 教给大家一个强大的数据结构——Doremy 树！现在她给你一个测验，以证明你在认真听课。 给定一个长度为 $ m $ 的数组 $ a $，Doremy 树支持查询 $ Q(l,r,k) $，其中 $ 1 \leq l \leq r \leq m $ 和 $ 1 \leq k \leq m $，返回数组 $ \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 $。你可以进行查询，在每次查询中，你给出三个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并收到 $ p $ 数组的 $ Q(l,r,k) $ 的值。你能否在最多 $ \mathbf{25} $ 次查询内找到索引 $ y $（$ 1 \leq y \leq n $），使得 $ p_y=1 $？ 注意，排列 $ p $ 在进行任何查询之前就已固定。 **输入输出格式** **输入格式** 你首先在第一行读取一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。 **输出格式** 为了进行查询，你应该输出： - "? $ l\ r\ k $"（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $） 在单独的一行中。每次查询后，你应该读取一个整数 $ x $——$ p $ 的 $ Q(l,r,k) $ 的值。在这个问题的版本中，你最多可以进行 $ 25 $ 次这样的查询。为了给出答案，你应该输出： - "! $ y $"（$ 1 \leq y \leq n $） 在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，别忘了输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用： - 在 C++ 中使用 fflush(stdout) 或 cout.flush()； - 在 Java 中使用 System.out.flush()； - 在 Pascal 中使用 flush(output)； - 在 Python 中使用 stdout.flush()； - 查看其他语言的文档。 **Hacks 格式** Hack 的第一行包含一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。 Hack 的第二行包含 $ 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] $。 输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。 在这个交互过程中： - 对于第一个查询，$\lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rf
- **这是一道交互题。**
- 交互库有一个 $[1,n]$ 的排列 $p$。
- 你可以询问 $l,r,k$，交互库会返回 $\left\lfloor\dfrac{p_l}k\right\rfloor,\left\lfloor\dfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\dfrac{p_r}k\right\rfloor$ 中不同数的个数。
- 你需要在 $25$ 次询问内找到 $p$ 中 $1$ 的位置。
- $n\in[3,1024]$。
**题目描述**
这个题目与其他两个版本的区别仅在于查询的最大次数。在这个版本中，你最多可以进行 $ \mathbf{25} $ 次查询。只有当所有版本的问题都解决后，你才能进行 hack。
这是一个交互问题。
“大家注意！Doremy 的完美数据结构课就要开始了！如果你想和我一样聪明，那就加油吧！” 在今天的 数据结构课 上，Doremy 教给大家一个强大的数据结构——Doremy 树！现在她给你一个测验，以证明你在认真听课。
给定一个长度为 $ m $ 的数组 $ a $，Doremy 树支持查询 $ Q(l,r,k) $，其中 $ 1 \leq l \leq r \leq m $ 和 $ 1 \leq k \leq m $，返回数组 $ \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 $。你可以进行查询，在每次查询中，你给出三个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并收到 $ p $ 数组的 $ Q(l,r,k) $ 的值。你能否在最多 $ \mathbf{25} $ 次查询内找到索引 $ y $（$ 1 \leq y \leq n $），使得 $ p_y=1 $？
注意，排列 $ p $ 在进行任何查询之前就已固定。
**输入输出格式**
**输入格式**
你首先在第一行读取一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。
**输出格式**
为了进行查询，你应该输出：
- "? $ l\ r\ k $"（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $）
在单独的一行中。每次查询后，你应该读取一个整数 $ x $——$ p $ 的 $ Q(l,r,k) $ 的值。在这个问题的版本中，你最多可以进行 $ 25 $ 次这样的查询。为了给出答案，你应该输出：
- "! $ y $"（$ 1 \leq y \leq n $）
在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，别忘了输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用：
- 在 C++ 中使用 fflush(stdout) 或 cout.flush()；
- 在 Java 中使用 System.out.flush()；
- 在 Pascal 中使用 flush(output)；
- 在 Python 中使用 stdout.flush()；
- 查看其他语言的文档。
**Hacks 格式**
Hack 的第一行包含一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。
Hack 的第二行包含 $ 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] $。
输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。
在这个交互过程中：
- 对于第一个查询，$\lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rf**题意翻译** - **这是一道交互题。** - 交互库有一个 $[1,n]$ 的排列 $p$。 - 你可以询问 $l,r,k$，交互库会返回 $\left\lfloor\dfrac{p_l}k\right\rfloor,\left\lfloor\dfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\dfrac{p_r}k\right\rfloor$ 中不同数的个数。 - 你需要在 $25$ 次询问内找到 $p$ 中 $1$ 的位置。 - $n\in[3,1024]$。 **题目描述** 这个题目与其他两个版本的区别仅在于查询的最大次数。在这个版本中，你最多可以进行 $ \mathbf{25} $ 次查询。只有当所有版本的问题都解决后，你才能进行 hack。 这是一个交互问题。 “大家注意！Doremy 的完美数据结构课就要开始了！如果你想和我一样聪明，那就加油吧！” 在今天的 数据结构课 上，Doremy 教给大家一个强大的数据结构——Doremy 树！现在她给你一个测验，以证明你在认真听课。 给定一个长度为 $ m $ 的数组 $ a $，Doremy 树支持查询 $ Q(l,r,k) $，其中 $ 1 \leq l \leq r \leq m $ 和 $ 1 \leq k \leq m $，返回数组 $ \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 $。你可以进行查询，在每次查询中，你给出三个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并收到 $ p $ 数组的 $ Q(l,r,k) $ 的值。你能否在最多 $ \mathbf{25} $ 次查询内找到索引 $ y $（$ 1 \leq y \leq n $），使得 $ p_y=1 $？ 注意，排列 $ p $ 在进行任何查询之前就已固定。 **输入输出格式** **输入格式** 你首先在第一行读取一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。 **输出格式** 为了进行查询，你应该输出： - "? $ l\ r\ k $"（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $） 在单独的一行中。每次查询后，你应该读取一个整数 $ x $——$ p $ 的 $ Q(l,r,k) $ 的值。在这个问题的版本中，你最多可以进行 $ 25 $ 次这样的查询。为了给出答案，你应该输出： - "! $ y $"（$ 1 \leq y \leq n $） 在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，别忘了输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用： - 在 C++ 中使用 fflush(stdout) 或 cout.flush()； - 在 Java 中使用 System.out.flush()； - 在 Pascal 中使用 flush(output)； - 在 Python 中使用 stdout.flush()； - 查看其他语言的文档。 **Hacks 格式** Hack 的第一行包含一个整数 $ n $（$ 3 \le n \le 1024 $）——排列的长度。 Hack 的第二行包含 $ 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] $。 输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。 在这个交互过程中： - 对于第一个查询，$\lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rf