[Solution] Fixed Point Guessing Codeforces Solution

[Solution] Fixed Point Guessing Codeforces Solution

D. Fixed Point Guessing

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

This is an interactive problem.

Initially, there is an array a=[1,2,…,n]$a=[1,2,\dots ,n]$, where n$n$ is an odd positive integer. The jury has selected n−12$\frac{n-1}{2}$ disjoint pairs of elements, and then the elements in those pairs are swapped. For example, if a=[1,2,3,4,5]$a=[1,2,3,4,5]$, and the pairs 1↔4$1\leftrightarrow 4$ and 3↔5$3\leftrightarrow 5$ are swapped, then the resulting array is [4,2,5,1,3]$[4,2,5,1,3]$.

As a result of these swaps, exactly one element will not change position. You need to find this element.

To do this, you can ask several queries. In each query, you can pick two integers l$l$ and r$r$ (1≤l≤r≤n$1\le l\le r\le n$). In return, you will be given the elements of the subarray [al,al+1,…,ar]$[a_l,a_{l+1},\dots ,a_r]$ sorted in increasing order.

Find the element which did not change position. You can make at most 15$\mathbf{15}$ queries.

The array a$a$ is fixed before the interaction and does not change after your queries.

Recall that an array b$b$ is a subarray of the array a$a$ if b$b$ can be obtained from a$a$ by deletion of several

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

Each test contains multiple test cases. The first line contains an integer t$t$ (1≤t≤500$1\le t\le 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer n$n$ (3≤n<104$3\le n<{10}^4$; n$n$ is odd) — the length of the array a$a$.

After reading the first line of each test case, you should begin the interaction.

XOR Mixup Codeforces Solution

Rising Sand Codeforces Solution

3SUM Closure Codeforces Solution

Fixed Point Guessing Codeforces Solution

PermutationForces II Codeforces Solution

Equal Reversal Codeforces Solution

Long Binary String Codeforces Solution

It is guaranteed that the sum of n$n$ over all test cases does not exceed 104${10}^4$.

Interaction

For each test case, begin the interaction by reading the integer n$n$.

To make a query, output "?lr$\mathtt{\text{?}}lr$" (1≤l≤r≤n$1\le l\le r\le n$) without quotes. Afterwards, you should read in r−l+1$r-l+1$ integers — the integers al,al+1,…,ar$a_l,a_{l+1},\dots ,a_r$, in increasing order. You can make at most 15$15$ such queries in a single test case.

If you receive the integer −1$-1$ instead of an answer or the integer n$n$, it means your program has made an invalid query, has exceed the limit of queries, or has given incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

When you are ready to give the final answer, output "!x$\mathtt{\text{!}}x$" (1≤x≤n$1\le x\le n$) without quotes — the element that did not change position. Giving this answer does not count towards the limit of 15$15$ queries. Afterwards, your program must continue to solve the remaining test cases, or exit if all test cases have been solved.

After printing a query do not forget to output 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

To make a hack, use the following format. The first line must contain an integer t$t$ (1≤t≤500$1\le t\le 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case must contain an integer n$n$ (3≤n<104$3\le n<{10}^4$; n$n$ is odd) — the length of the array a$a$.

The second line of each test case must contain n$n$ space-separated integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤n$1\le a_i\le n$) — the elements of a$a$. The array a$a$ should be the result of n−12$\frac{n-1}{2}$ disjoint swaps on the array [1,2,…,n]$[1,2,\dots ,n]$.