309956: CF1764G3. Doremy's Perfect DS Class (Hard Version)
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Doremy's Perfect DS Class (Hard 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$ 中不同数的个数。 - 你需要在 $20$ 次询问内找到 $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{20} $ 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{20} $ 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 $ 20 $ 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$ 中不同数的个数。 - 你需要在 $20$ 次询问内找到 $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$ 中不同数的个数。
- 你需要在 $20$ 次询问内找到 $p$ 中 $1$ 的位置。
- $n\in[3,1024]$。
**题目描述**
这个问题与其他两个版本唯一的不同是查询的最大数量。在这个版本中，你最多可以进行 $ \mathbf{20} $ 次查询。只有当所有版本的问题都解决后，你才能进行破解。
这是一个交互问题。
“大家注意！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 $。你可以进行查询，在每次查询中，你给出 $ 3 $ 个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并获得数组 $ p $ 的 $ Q(l,r,k) $ 值。你可以在最多 $ \mathbf{20} $ 次查询中找到索引 $ 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) $ 值。在这个问题的版本中，你最多可以进行 $ 20 $ 次这样的查询。为了给出答案，你应该输出：
- "! $ y $"（$ 1 \leq y \leq n $）
在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用：
- 在C++中：fflush(stdout) 或 cout.flush();
- 在Java中：System.out.flush();
- 在Pascal中：flush(output);
- 在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] $。
输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。
在这个交互过程中：
- 对于第一次查询，$ \lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=**题意翻译** - **这是一道交互题。** - 交互库有一个 $[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$ 中不同数的个数。 - 你需要在 $20$ 次询问内找到 $p$ 中 $1$ 的位置。 - $n\in[3,1024]$。 **题目描述** 这个问题与其他两个版本唯一的不同是查询的最大数量。在这个版本中，你最多可以进行 $ \mathbf{20} $ 次查询。只有当所有版本的问题都解决后，你才能进行破解。 这是一个交互问题。 “大家注意！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 $。你可以进行查询，在每次查询中，你给出 $ 3 $ 个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并获得数组 $ p $ 的 $ Q(l,r,k) $ 值。你可以在最多 $ \mathbf{20} $ 次查询中找到索引 $ 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) $ 值。在这个问题的版本中，你最多可以进行 $ 20 $ 次这样的查询。为了给出答案，你应该输出： - "! $ y $"（$ 1 \leq y \leq n $） 在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用： - 在C++中：fflush(stdout) 或 cout.flush(); - 在Java中：System.out.flush(); - 在Pascal中：flush(output); - 在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] $。 输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。 在这个交互过程中： - 对于第一次查询，$ \lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=
- **这是一道交互题。**
- 交互库有一个 $[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$ 中不同数的个数。
- 你需要在 $20$ 次询问内找到 $p$ 中 $1$ 的位置。
- $n\in[3,1024]$。
**题目描述**
这个问题与其他两个版本唯一的不同是查询的最大数量。在这个版本中，你最多可以进行 $ \mathbf{20} $ 次查询。只有当所有版本的问题都解决后，你才能进行破解。
这是一个交互问题。
“大家注意！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 $。你可以进行查询，在每次查询中，你给出 $ 3 $ 个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并获得数组 $ p $ 的 $ Q(l,r,k) $ 值。你可以在最多 $ \mathbf{20} $ 次查询中找到索引 $ 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) $ 值。在这个问题的版本中，你最多可以进行 $ 20 $ 次这样的查询。为了给出答案，你应该输出：
- "! $ y $"（$ 1 \leq y \leq n $）
在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用：
- 在C++中：fflush(stdout) 或 cout.flush();
- 在Java中：System.out.flush();
- 在Pascal中：flush(output);
- 在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] $。
输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。
在这个交互过程中：
- 对于第一次查询，$ \lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=**题意翻译** - **这是一道交互题。** - 交互库有一个 $[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$ 中不同数的个数。 - 你需要在 $20$ 次询问内找到 $p$ 中 $1$ 的位置。 - $n\in[3,1024]$。 **题目描述** 这个问题与其他两个版本唯一的不同是查询的最大数量。在这个版本中，你最多可以进行 $ \mathbf{20} $ 次查询。只有当所有版本的问题都解决后，你才能进行破解。 这是一个交互问题。 “大家注意！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 $。你可以进行查询，在每次查询中，你给出 $ 3 $ 个整数 $ l,r,k $（$ 1 \leq l \leq r \leq n $，$ 1 \leq k \leq n $），并获得数组 $ p $ 的 $ Q(l,r,k) $ 值。你可以在最多 $ \mathbf{20} $ 次查询中找到索引 $ 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) $ 值。在这个问题的版本中，你最多可以进行 $ 20 $ 次这样的查询。为了给出答案，你应该输出： - "! $ y $"（$ 1 \leq y \leq n $） 在单独的一行中，其中 $ p_y=1 $。在打印查询或答案后，不要忘记输出行尾并刷新输出。否则，你会得到超时限制。为此，请使用： - 在C++中：fflush(stdout) 或 cout.flush(); - 在Java中：System.out.flush(); - 在Pascal中：flush(output); - 在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] $。 输入和输出示例说明了可能的交互过程（仅为了清晰起见插入空行）。 在这个交互过程中： - 对于第一次查询，$ \lfloor\frac{3}{4}\rfloor=0,\lfloor\frac{5}{4}\rfloor=1,\lfloor\frac{2}{4}\rfloor=