{"problem":{"name":"[NordicOI 2022] 夸克显微镜 Quark Microscopy","description":{"content":"这下可惨了！Niels 珍爱的原子被宇宙射线击中，分裂成了许多夸克。Niels 迫切地想要找到这些夸克，然后将它们拼起来。所以，他找来了你来帮忙。 这 $N$ 个夸克分布在一条 $1$ 米（$10^{18}$ 阿米）长的线段上。幸运的是，你有一个很精确，但有点奇怪的夸克显微镜，它能够检测并测量邻近的夸克。然而由于量子效应，它无法直接告诉你离测量位置最近的夸克的位置，而是会告诉你离测量位置第二近的","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10645"},"statements":[{"statement_type":"Markdown","content":"这下可惨了！Niels 珍爱的原子被宇宙射线击中，分裂成了许多夸克。Niels 迫切地想要找到这些夸克，然后将它们拼起来。所以，他找来了你来帮忙。\n\n这 $N$ 个夸克分布在一条 $1$ 米（$10^{18}$ 阿米）长的线段上。幸运的是，你有一个很精确，但有点奇怪的夸克显微镜，它能够检测并测量邻近的夸克。然而由于量子效应，它无法直接告诉你离测量位置最近的夸克的位置，而是会告诉你离测量位置第二近的夸克的位置，以及离测量位置第二近的夸克的数量。\n\n更为准确地说，你可以在线段上的位置 $x$ 处进行测量。对于每次测量，每个夸克距 $x$ 的距离将会被测出并升序排序，记为 $d_1,d_2,\\cdots,d_N$。你会得到 $d_2$，和满足 $d_i=d_2$ 的 $i$ 的数量（只会是 $1$ 或 $2$）。在进行足够多次测量后，你需要回答每个夸克所在的位置。\n\n每个夸克的位置都是介于 $[1,10^{18}]$ 间的正整数（单位：阿米），从线段的起始位置开始计算。由于 Pauli 不相容原理，夸克的位置不会重合。\n\n## Input\n\n你的程序与交互库通过标准输入输出流交互。\n\n第一行，两个正整数 $N,T$，表示夸克的数量和子任务编号。\n\n接下来，你的程序开始与交互库交互：\n\n- `? x`：询问离 $x$ 第二远的夸克。交互库会返回两个整数 $r,m$，其中 $r$ 是第二远夸克的距离，$m$ 是距离 $x$ 为 $r$ 的夸克的数量（只会是 $1$ 或 $2$）。你需要保证 $-10^{18}\\le x\\le 2\\times 10^{18}$。\n\n- `!` $a_1$ $a_2$ $\\cdots$ $a_N$：回答夸克的位置。你可以以任意顺序给出这些夸克的位置。回答后，不应有多余的询问。你需要保证 $1\\le a_i\\le 10^{18}$。\n\n**注意：在交互过程中，你需要在输出后刷新缓存区。**\n下面是一些常见语言的刷新缓存区方式：\n\n- C++：`fflush(stdout)` 或 `cout.flush()`。特别地，利用 `std::endl` 换行也会刷新缓冲区。\n- C：`fflush(stdout)`。\n\n## Output\n\n见【输出格式】。\n\n[samples]\n\n## Background\n\n译自 Nordic Olympiad in Informatics 2022  [Quark Microscopy](https://noi22.kattis.com/contests/noi22/problems/quarkmicroscopy)。如果发现交互库锅了请联系搬题人 qvq。\n\n$\\texttt{1s,1G}$。\n\n## Note\n\n#### 数据范围\n\n- $3\\le N\\le 100$；\n- $1\\le T\\le 3$。\n\n#### 评分方式\n\n| 子任务编号 | 得分 | 限制 |\n| :--: | :--: | :--: |\n| $1$ | $40\\cdot r$ |  存在一个在位置 $1$ 上的夸克 |\n| $2$ | $40\\cdot r$ | 夸克的位置均为偶数 |\n| $3$ | $20\\cdot r$ | 无额外限制 |\n\n其中 $r$ 为一个常数。记某个子任务中你查询的最大次数为 $Q$，则 $r$ 的值见以下表格：\n\n| $Q$ 的限制 | $r=$ |\n| :--: | :--: |\n| $Q\\gt 15\\, 000$ | $0$ |\n| $15\\, 000\\ge Q\\gt 5\\, 600$ | $0.4$ |\n| $5\\, 600\\ge Q\\gt 3\\, 500$ | $0.6$ |\n| $3\\, 500\\ge Q\\gt 2\\, 400$ | $0.8$ |\n| $Q\\le 2\\, 400$ | $1.0$ |\n\n为了方便选手测试，我们提供了 `testing_tools.py`，可在附件下载，使用说明见文件头。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10645","tags":["2022","交互题","Special Judge","NordicOI（北欧）"],"sample_group":[["3 3\n\n6 1\n\n4 1\n\n1 2","\n? 5\n\n? 15\n\n? 11\n\n! 11 10 12"],["3 1\n\n2 1\n\n1 2\n\n2 1\n\n45 1","\n? 1\n\n? 2\n\n? 3\n\n? 47\n\n! 1 3 92"]],"created_at":"2026-03-03 11:09:25"}}