{"problem":{"name":"「RiOI-03」Just a Q. (Hard ver.)","description":{"content":"**这是一道交互题。** 小 R 有一个变量 $Q$。$Q$ 初始为 $0$。 小 R 有 $n$ 个隐藏的整数 $q_1 \\dots q_n$，满足 $1 \\leq \\lvert q_i \\rvert \\leq V$，且有且仅有一个 $i$ 满足 $q_i \\lt 0$，而面前的你，需要得出这个满足 $q_i \\lt 0$ 的下标 $i$。 小 R 承诺不会让你以仅仅 $\\frac{1}{","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1800,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9918"},"statements":[{"statement_type":"Markdown","content":"**这是一道交互题。**\n\n小 R 有一个变量 $Q$。$Q$ 初始为 $0$。\n\n小 R 有 $n$ 个隐藏的整数 $q_1 \\dots q_n$，满足 $1 \\leq \\lvert q_i \\rvert \\leq V$，且有且仅有一个 $i$ 满足 $q_i \\lt 0$，而面前的你，需要得出这个满足 $q_i \\lt 0$ 的下标 $i$。\n\n小 R 承诺不会让你以仅仅 $\\frac{1}{n}$ 的几率盲猜，所以她可以允许你进行最多 $k$ 次询问。每次询问，你可以向小 R 给出**可重**正整数集合 $S$ 满足 $0 \\leq \\lvert S \\rvert \\leq S_{\\max}$ 且 $\\forall i \\in S, i \\leq n$，她会计算 $M = \\prod\\limits_{i\\in S}q_i$，然后让 $Q \\leftarrow Q + M$。特殊地，若 $S$ 为空集，则 $M = 1$。\n\n一次询问后，小 R 会向你给出此时的 $\\text{sgn}(Q)$（为 `+`，`-` 或 `0`），表示 $Q$ 的符号。具体地，若 $Q \\gt 0$，小 R 返回 `+`；若 $Q \\lt 0$，小 R 返回 `-`；否则返回 `0`。\n\n请你在不超过 $k$ 次询问后，找到那个满足 $q_i \\lt 0$ 的下标 $i$。\n\n**保证对于所有数据，满足 $q_i \\lt 0$ 的下标 $i$ 是在 $[1, n]$ 内均匀随机选取的。请注意报告下标属于一次询问。**\n\n## Input\n\n### 交互格式\n\n第一行，输入三个正整数 $n, k, S_{\\max}$。\n\n在此之后，你应当进行若干次询问。\n\n对于你的每组询问，输出 $?\\ m\\ s_1\\ s_2 \\dots s_m$，表示给出一个**可重**正整数集合 $S$，其大小为 $m$，你需要保证 $0 \\leq m \\leq S_{\\max}$。此外，同时应有 $1 \\leq s_i \\leq n$，描述这个集合里的元素编号。\n\n如果你已经得到答案，请输出 $!\\ i$，满足 $1 \\leq i \\leq n$，代表你得到 $q_i \\lt 0$，在这之后你应当立即退出本轮交互。\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每次询问并刷新缓冲区后，你将从标准输入中输入一个字符，字符为 `+`，`-` 或 `0`，表示当前 $Q$ 的符号 $\\text{sgn}(Q)$。\n\n### 输入格式\n\n本题有多组数据。\n\n第一行，一个整数 $T$ 表示数据组数。\n\n对于每一组数据，请按照 **【交互格式】** 进行交互。当你报告下标后：\n\n+ 如果你给出的下标正确：\n\t+ 如果这是最后一组数据，交互库退出并返回 Accepted；\n\t+ 如果这不是最后一组数据，你应当接着读入 $n, k, S_{\\max}$ 以进行下一组数据的交互。\n+ 否则，下标错误，交互库会立刻终止，返回 Unaccepted。\n\n## Output\n\n见 **【输入格式】**。\n\n[samples]\n\n## Background\n\n「Yes, I am Q.」\n\n面前的小 R 莞尔一笑。\n\n+ 保证本题的任何合理的部分分或正解的 std + spj 均可以在当前数据下，$900$ ms 的时间限制、$32$ MB 的空间限制内正确运行并获得 AC 状态。\n+ 本题不添加仅为无意义地卡满 spj 运行时间的 hack 数据。\n\n**请注意，本题只有约束范围与普通版不同，且两个版本的约束范围并不完全重叠。**\n\n## Note\n\n### 样例解释 1\n\n$q = \\{-1, 1, 4, 5, 1, 4\\}$。\n\n### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | $n \\leq$ | $T \\leq$ | $k = $ | $S_{\\max} = $ | 分值 |\n| :-: | :-: | :-: | :-: | :-: | :-: |\n| $0$ | $200$ | $500$ | $20$ | $20n + 1$ | $11$ |\n| $1$ | $1000$ | $50$ | $41$ | $8n + 10$ | $25$ |\n| $2$ | $1000$ | $50$ | $50$ | $6n + 10$ | $30$ |\n| $3$ | $10^4$ | $10$ | $39$ | $\\lceil 1.5n\\rceil + 10$ | $34$ |\n\n对于子任务 $0, 1, 3$，若通过所有测试点则获得全部分数，否则获得 $0$ 分。\n\n对于子任务 $2$：\n\n+ 你需要保证你所使用的实际操作次数 $k'$ 满足 $0 \\leq k' \\leq 50$。\n+ 你需要保证你所使用的实际操作次数 $S'$ 满足 $0 \\leq S' \\leq 6n + 10$。\n+ 单个测试点的得分为 $\\left(1 - \\max(\\frac{\\max k' - 35}{20}, \\max(\\frac{S' - 3n - 10}{4n + 1}), 0)\\right)\\times 30$。\n+ Subtask 的得分取所有测试点的得分最小值。\n\n对于所有数据，$1 \\leq V \\leq 10^6$，$1 \\leq n \\leq 10^4$，$1 \\leq T \\leq 500$，**注意由于交互库限制 $\\bm{n, T}$ 不会同时取到最大值**；此外，对每个子任务 $k, S_{\\max}$ 的值已经给出。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9918","tags":["数学","二分","洛谷原创","交互题","Special Judge","O2优化","洛谷月赛","Ad-hoc"],"sample_group":[["1\n6 6 6\n\n-\n\n-\n\n-\n\n+\n\n0\n\n\n","\n\n? 1 1\n\n? 5 1 2 3 4 5\n\n? 3 2 4 6\n\n? 1 4\n\n? 3 1 5 6\n\n! 1"]],"created_at":"2026-03-03 11:09:25"}}