2173E. Shiro's Mirror Duel

constructive algorithms, greedy, interactive, probabilities, sortings, 2200,

https://codeforces.com/problemset/problem/2173/E

There's no such thing as luck in this world. The victor is decided before the game even starts.

— No Game No Life

This is an interactive problem.

One day, Sora and Shiro feel bored again, so they decide to settle it with a game.

At the beginning, Sora gives Shiro a permutation∗ 𝑝1,𝑝2,…,𝑝𝑛 of length 𝑛. In each operation, Shiro may select two distinct indices 𝑥and 𝑦 (1≤𝑥≠𝑦≤𝑛). Then Sora flips a fair coin:

With probability 0.5, Sora swaps 𝑝𝑥 and 𝑝𝑦;
With probability 0.5, Sora swaps 𝑝𝑛−𝑥+1 and 𝑝𝑛−𝑦+1.

After the operation, Sora replies with the actual pair of indices that were swapped, so that Shiro can update her local permutation accordingly.

Shiro's goal is to sort the permutation 𝑝 in ascending order by using at most ⌊2.5𝑛+800⌋ operations. Help her!

∗A permutation of length 𝑛 is an array consisting of 𝑛 distinct integers from 1 to 𝑛 in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array), and [1,3,4] is also not a permutation (𝑛=3 but there is 4 in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤100). The description of the test cases follows.

The first line of each test case contains a single integer 𝑛 (1≤𝑛≤4000) — the length of 𝑝.

The second line contains 𝑛 integers 𝑝1,𝑝2,…,𝑝𝑛 — the elements of 𝑝.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 2⋅104.

It is guaranteed that there are 50 tests in this problem.

Interaction

For each test case, you can use at most ⌊2.5𝑛+800⌋ moves to sort the permutation 𝑝 in ascending order.

To make a move, you should print a new line in the following format:

?𝑥𝑦 (1≤𝑥≠𝑦≤𝑛) — the two indices that Shiro selects in this move.

As a response to the move, you will receive two integers 𝑢 and 𝑣 — the actual pair of indices that Sora swapped. It is guaranteed that (𝑢,𝑣) is randomly selected from (𝑥,𝑦) and (𝑛−𝑥+1,𝑛−𝑦+1) with equal probability.

To report that the permutation has been sorted in ascending order, you should print a new line with a single character !. This does notcount as one of the ⌊2.5𝑛+800⌋ moves.

After that, proceed to the next test case or terminate the program if it was the last test case.

After printing each query do not forget to output the end of line and flush∗ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read −1 instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks are disabled in this problem.

∗To flush, use:

fflush(stdout) or cout.flush() in C++;
sys.stdout.flush() in Python;
see the documentation for other languages.

Example

input

output

? 1 5

? 4 5

!


!

Note

In the first test case, 𝑛=5 and the initial permutation is [5,1,3,4,2].

We print ? 1 5. The judge replies 1 5, meaning positions 1 and 5 are swapped (no mirroring). The array becomes [2,1,3,4,5].
We print ? 4 5. The judge replies 2 1, which is the mirror of 4,5 because with 𝑛=5 we have 𝑛−4+1=2 and 𝑛−5+1=1. Thus we must swap positions 2 and 1. The array becomes [1,2,3,4,5].
The permutation is now sorted, so we print !. The answer line does not count toward the operation limit.

In the second test case, the given permutation is already increasing, so we just need to output !.

【尹显齐 2500011456 物理学院】

因为有可能在两个对称的位置进行交换，所以我们的排序必须从两头向中间进行。假设现在我们要将 $a_{i}$ 和 $a_{n - i}$ 同时变成 $i$ 和 $n - i$ 。

第一步：先将 $a_{i}$ 变成 $i$ ，输入的操作为交换 $i$ 和 $a_{i}$ 即可。平均需要 $2$ 步。
第二步：保持 $i$ 位置不动的同时让 $a_{n - i}$ 变成 $n - i$ 。输入的操作为交换 $n - i$ 和 $a_{n - i}$ 。假设平均需要 $x$ 步完成，下一步有可能将 $a_{n - i}$ 换到指定位置上，也有可能将 $i$ 换走。在第二种情况下，再操作一步，一定会有一个数在自己对应位置上。所以可以列出等式

x = 0.5 + 0.5 (2 + x)

计算得出平均需要 $3$ 步。
所以，在此方法下，将 $2$ 个数排好位置，平均需要 $5$ 步，那么将 $n$ 个数全部排好，平均需要 $2.5 n$ 步，满足题目要求。

代码：

python

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    data = {}# 用data存储所有数的位置，便于输出
    for i,a in enumerate(arr):
        data[a] = i
    i = 0
    while i <= (n-1)//2:
        if arr[i] != i+1 or arr[n-1-i] != n-i:
        # 先排好第一个数
            while arr[i] != i+1:
                print(f"? {data[i+1]+1} {i+1}")
                x,y = map(int,input().split())
                data[arr[x-1]] = y-1
                data[arr[y-1]] = x-1
                arr[x-1],arr[y-1] = arr[y-1],arr[x-1]
            a = data[n-i]+1
        # 接着排第二个数
            while arr[n-1-i] != n-i or arr[i] != i+1:
                print(f"? {a} {n-i}")
                x,y = map(int,input().split())
                data[arr[x-1]] = y-1
                data[arr[y-1]] = x-1
                arr[x-1],arr[y-1] = arr[y-1],arr[x-1]    
        i += 1
    print("!")

2173E. Shiro's Mirror Duel ​

2173E. Shiro's Mirror Duel