{"problem":{"name":"「TAOI-1」Antipathy World","description":{"content":"**这是一道 IO 交互题。** 可不有 $n$ 朵花，每朵花有一个正整数美丽度。 她发现，有一朵花的美丽度不小于其它任何一朵花的美丽度的两倍。 你想知道这朵花是哪一朵，于是你可以进行至多 $k$ 次询问，每次询问你给出两个正整数 $i,j \\in [1, n]$，可不会告诉你第 $i$ 朵和第 $j$ 朵花的美丽度之差的绝对值。 你想运用这些询问的答案，得到最美丽的花是第几朵。 ###","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9219"},"statements":[{"statement_type":"Markdown","content":"**这是一道 IO 交互题。**\n\n可不有 $n$ 朵花，每朵花有一个正整数美丽度。\n\n她发现，有一朵花的美丽度不小于其它任何一朵花的美丽度的两倍。\n\n你想知道这朵花是哪一朵，于是你可以进行至多 $k$ 次询问，每次询问你给出两个正整数 $i,j \\in [1, n]$，可不会告诉你第 $i$ 朵和第 $j$ 朵花的美丽度之差的绝对值。\n\n你想运用这些询问的答案，得到最美丽的花是第几朵。\n\n### 交互格式\n\n**本题有多组数据**。\n\n第一行交互库给出一个整数 $T$，表示数据组数。\n\n对于每组数据，第一行输入两个正整数 $n,k$。\n\n对于你的每组询问，你输出 `? i j`，交互库会返回一个非负整数，表示第 $i$ 朵和第 $j$ 朵花的美丽度之差。\n\n如果你已经得到答案，输出 `! i` 代表你得到第 $i$ 朵花为最美丽的花。在此之后你应该开始对下一组数据的处理。\n\n每次你输出之后，请**刷新缓冲区**。\n\n你可以使用如下语句来清空缓冲区：\n\n- 对于 C/C++：`fflush(stdout)`；\n- 对于 C++：`std::cout << std::flush`；\n- 对于 Java：`System.out.flush()`；\n- 对于 Python：`stdout.flush()`；\n- 对于 Pascal：`flush(output)`；\n- 对于其他语言，请自行查阅对应语言的帮助文档。\n\n特别的，对于 C++ 语言，在输出换行时如果你使用 `std::endl` 而不是 `'\\n'`，也可以自动刷新缓冲区。\n\n## Input\n\n见「交互格式」。\n\n## Output\n\n见「交互格式」。\n\n[samples]\n\n## Background\n\n> 簡単なことも解らないわ \\\n> あたしって何だっけ \\\n> それすら夜の手に絆されて \\\n> 愛のように 消える 消える \\\n> さようならも言えぬ儘泣いた フォニイ フォニイ フォニイ \\\n> 嘘に絡まっているあたしはフォニイ \\\n> **ANTIPATHY WORLD**\n\n## Note\n\n样例中给出了一种可能的交互方式，其中花的美丽度为 $\\{4,1,2\\}$。\n\n---\n\n**本题采用捆绑测试**。\n\n- Subtask 1（20 points）：$k=\\dfrac{n(n-1)}{2}$，$n \\le 200$。\n- Subtask 2（30 points）：$k=n$。\n- Subtask 3（50 points）：$k=\\left\\lfloor\\dfrac{n}{2}\\right\\rfloor+2$。\n\n对于所有测试数据，设所有花的美丽度为 $a_i$，$1 \\le T \\le 25$，$3 \\le n \\le 5 \\times 10^4$，$1 \\le a_i \\le 10^8$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9219","tags":["交互题","Special Judge","O2优化"],"sample_group":[["1\n3 114514\n\n3\n\n2\n\n1\n","\n\n? 1 2\n\n? 1 3\n\n? 2 3\n\n! 1"]],"created_at":"2026-03-03 11:09:25"}}