---
title: "Codeforces Round 770 (Div. 2) D(互動)"
tags: 題解, 互動, 數論
---

https://codeforces.com/contest/1634/problem/D

#### 題意

有一個長度 $N$ 的數組，只有正整數和唯一的一個零。每次 query 給出 $i, j, k$ 三個不重複位置，會得到三個位置上的值的最大值減最小值。

求在最多 query $2N-2$ 次的情況下，回答零可能在的兩個位置。

#### 思路

假設四個數 $a, b, c, d$ 滿足 $a = 0$, $b <= c <= d$，則考慮每次去掉一個數的四組 query：

$query(a, b, c) = max(a, b, c) - min(a, b, c) = c$
$query(a, b, d) = max(a, b, d) - min(a, b, d) = d$
$query(a, c, d) = max(a, c, d) - min(a, c, d) = d$
$query(b, c, d) = max(b, c, d) - min(b, c, d) = d - b$

觀察得知：回傳最大值 $d$ 的兩組 query，去掉的數必定是最大值 ($d$) 與零 ($a$) 以外的兩個數 ($b$ 和 $c$)。

因此我們可以每四個數就刪掉兩個數，最後剩下的若是兩個數則直接回答，若是三個數則隨便放入一個已經被刪掉的數然後再刪掉不可能的兩個數。

#### Code

def query(args):
    print("? {}".format(" ".join(str(c) for c in args)), flush=True)
    return int(input())

def answer(args):
    print("! {}".format(" ".join(str(c) for c in args)), flush=True)

def solve():
    def go():
        nonlocal back
        v = [(query(m), arr[~idx]) for idx, m in enumerate(combinations(arr, 3))]
        v.sort()
        back = v[-1][1]
        arr.remove(v[-1][1])
        arr.remove(v[-2][1])

    N = int(input())

    back = -1
    arr = []
    for i in range(1, N + 1):
        arr.append(i)
        if len(arr) == 4: go()

    if len(arr) == 3:
        arr.append(back)
        go()

    answer(arr)

if __name__ == "__main__":
    for i in range(int(input())):
        solve()