2162D.md (4426B)
1 Source: https://codeforces.com/problemset/problem/2162/D 2 3 D. Beautiful Permutation 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is an interactive problem. 22 23 There is a permutation$^{\text{∗}}$ $p$ of length $n$. 24 25 Someone secretly chose two integers $l, r$ ($1 \le l \le r \le n$) and modified the permutation in the following way: 26 27 * For every index $i$ such that $l \le i \le r$, set $p_i := p_i + 1$. 28 29 Let $a$ denote the resulting array obtained by modifying the permutation. 30 31 You are given an integer $n$ denoting the length of the permutation $p$. 32 33 In one query, you are allowed to choose two integers $l, r$ ($1 \le l \le r \le n$) and ask for the sum of the subarray either of the original permutation $p[l \dots r]$ or of the modified array $a[l \dots r]$. The answer to such a query will be the corresponding integer sum. 34 35 Your task is to find the pair $(l, r)$ that was chosen to obtain $a$ in no more than $\bf{40}$ queries. 36 37 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (the number $2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$, but the array contains $4$). 38 39 Input 40 41 The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 42 43 Each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^4$) — the length of the permutation. 44 45 It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot10^4$. 46 47 Interaction 48 49 The interaction for each test case begins by reading the integer $n$. 50 51 You can ask two types of queries. 52 53 * Print "$ \texttt{1 l r} $" ($1 \le l \le r \le n$). 54 55 In response, you should read a line containing a single integer $x$ — the sum of the subarray of the original permutation. (Formally, $x = p_l + p_{l + 1} + \dots + p_r$). 56 * Print "$ \texttt{2 l r} $" ($1 \le l \le r \le n$). 57 58 In response, you should read a line containing a single integer $y$ — the sum of the subarray of the modified array. (Formally, $y = a_l + a_{l + 1} + \dots + a_r$). 59 60 The permutation $p$ and the chosen integers $l$, $r$ are fixed beforehand and can't be changed during the time of interaction. 61 62 You can output the final answer by printing "$ \texttt{! l r} $", where $l$, $r$ denote the integers that were chosen to obtain $a$. After printing the answer, your program should proceed to the next test case or terminate if there are no more. 63 64 You can ask no more than $40$ queries per testcase. Printing the answer doesn't count as a query. If your program performs more than $40$ queries for one test case or makes an invalid query, you may receive a Wrong Answer verdict. 65 66 After printing a query, do not forget to output the end of line and flush$^{\text{∗}}$ the output. Otherwise, you will get Idleness limit exceeded. 67 68 Hacks 69 70 To make a hack, use the following test format. 71 72 The first line should contain a single integer $t$ $(1 \le t \le 10^4)$ — the number of testcases. 73 74 The first line of each test case should contain a single integer $n$ ($1 \le n \le 2\cdot10^4$) — the length of the permutation $p$. 75 76 The second line of each test case should contain $n$ integers $p_i$ ($1 \le p_i \le n$) — denoting the permutation $p$. 77 78 The third line of each test case should contain two space-separated integers $l$, $r$ ($1 \le l \le r \le n$) — the chosen integers. 79 80 For example, the following is the hack format of the example test: 81 82 ``` 83 2 84 3 85 3 1 2 86 2 2 87 4 88 2 1 3 4 89 2 4 90 ``` 91 92 $^{\text{∗}}$To flush, use: 93 94 * fflush(stdout) or cout.flush() in C++; 95 * System.out.flush() in Java; 96 * flush(output) in Pascal; 97 * stdout.flush() in Python; 98 * see documentation for other languages 99 100 Example 101 102 Input 103 104 ``` 105 2 106 107 3 108 109 4 110 111 5 112 113 4 114 115 8 116 117 8 118 119 9 120 ``` 121 122 Output 123 124 ``` 125 1 1 2 126 127 2 1 2 128 129 ! 2 2 130 131 1 2 4 132 133 2 1 3 134 135 2 3 4 136 137 ! 2 4 138 ``` 139 140 Note 141 142 For the first testcase, $p = [3, 1, 2]$ and $l = 2$, $r = 2$. Hence, the modified array $a$ will be equal to $[3, 2, 2]$. 143 144 So, querying "$\texttt{1 1 2}$" gives $p_1 + p_2 = 3 + 1 = 4$. And querying "$\texttt{2 1 2}$" gives $a_1 + a_2 = 3 + 2 = 5$. 145 146 For the second testcase, $p = [2, 1, 3, 4]$ and $l = 2$, $r = 4$. 147 148 Note that the queries shown in the sample test are only for demonstration purposes, and they may not correspond to any optimal solution.