luogu#P9918. 「RiOI-03」Just a Q. (Hard ver.)

    ID: 13885 远端评测题 1800ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>数学二分洛谷原创交互题Special JudgeO2优化洛谷月赛Ad-hoc

「RiOI-03」Just a Q. (Hard ver.)

题目背景

「Yes, I am Q.」

面前的小 R 莞尔一笑。

  • 保证本题的任何合理的部分分或正解的 std + spj 均可以在当前数据下,900900 ms 的时间限制、3232 MB 的空间限制内正确运行并获得 AC 状态。
  • 本题不添加仅为无意义地卡满 spj 运行时间的 hack 数据。

请注意,本题只有约束范围与普通版不同,且两个版本的约束范围并不完全重叠。

题目描述

这是一道交互题。

小 R 有一个变量 QQQQ 初始为 00

小 R 有 nn 个隐藏的整数 q1qnq_1 \dots q_n,满足 1qiV1 \leq \lvert q_i \rvert \leq V,且有且仅有一个 ii 满足 qi<0q_i \lt 0,而面前的你,需要得出这个满足 qi<0q_i \lt 0 的下标 ii

小 R 承诺不会让你以仅仅 1n\frac{1}{n} 的几率盲猜,所以她可以允许你进行最多 kk 次询问。每次询问,你可以向小 R 给出可重正整数集合 SS 满足 0SSmax0 \leq \lvert S \rvert \leq S_{\max}iS,in\forall i \in S, i \leq n,她会计算 M=iSqiM = \prod\limits_{i\in S}q_i,然后让 QQ+MQ \leftarrow Q + M。特殊地,若 SS 为空集,则 M=1M = 1

一次询问后,小 R 会向你给出此时的 sgn(Q)\text{sgn}(Q)(为 +-0),表示 QQ 的符号。具体地,若 Q>0Q \gt 0,小 R 返回 +;若 Q<0Q \lt 0,小 R 返回 -;否则返回 0

请你在不超过 kk 次询问后,找到那个满足 qi<0q_i \lt 0 的下标 ii

保证对于所有数据,满足 qi<0q_i \lt 0 的下标 ii 是在 [1,n][1, n] 内均匀随机选取的。请注意报告下标属于一次询问。

输入格式

交互格式

第一行,输入三个正整数 n,k,Smaxn, k, S_{\max}

在此之后,你应当进行若干次询问。

对于你的每组询问,输出 ? m s1 s2sm?\ m\ s_1\ s_2 \dots s_m,表示给出一个可重正整数集合 SS,其大小为 mm,你需要保证 0mSmax0 \leq m \leq S_{\max}。此外,同时应有 1sin1 \leq s_i \leq n,描述这个集合里的元素编号。

如果你已经得到答案,请输出 ! i!\ i,满足 1in1 \leq i \leq n,代表你得到 qi<0q_i \lt 0,在这之后你应当立即退出本轮交互。

每次你输出之后,请刷新缓冲区

你可以使用如下语句来清空缓冲区:

  • 对于 C/C++:fflush(stdout)
  • 对于 C++:std::cout << std::flush
  • 对于 Java:System.out.flush()
  • 对于 Python:stdout.flush()
  • 对于 Pascal:flush(output)
  • 对于其他语言,请自行查阅对应语言的帮助文档。

特别的,对于 C++ 语言,在输出换行时如果你使用 std::endl 而不是 '\n',也可以自动刷新缓冲区。

每次询问并刷新缓冲区后,你将从标准输入中输入一个字符,字符为 +-0,表示当前 QQ 的符号 sgn(Q)\text{sgn}(Q)

输入格式

本题有多组数据。

第一行,一个整数 TT 表示数据组数。

对于每一组数据,请按照 【交互格式】 进行交互。当你报告下标后:

  • 如果你给出的下标正确:
    • 如果这是最后一组数据,交互库退出并返回 Accepted;
    • 如果这不是最后一组数据,你应当接着读入 n,k,Smaxn, k, S_{\max} 以进行下一组数据的交互。
  • 否则,下标错误,交互库会立刻终止,返回 Unaccepted。

输出格式

【输入格式】

1
6 6 6

-

-

-

+

0





? 1 1

? 5 1 2 3 4 5

? 3 2 4 6

? 1 4

? 3 1 5 6

! 1

提示

样例解释 1

q={1,1,4,5,1,4}q = \{-1, 1, 4, 5, 1, 4\}

数据规模与约定

本题采用捆绑测试。

子任务编号 nn \leq TT \leq k=k = Smax=S_{\max} = 分值
00 200200 500500 2020 20n+120n + 1 1111
11 10001000 5050 4141 8n+108n + 10 2525
22 5050 6n+106n + 10 3030
33 10410^4 1010 3939 1.5n+10\lceil 1.5n\rceil + 10 3434

对于子任务 0,1,30, 1, 3,若通过所有测试点则获得全部分数,否则获得 00 分。

对于子任务 22

  • 你需要保证你所使用的实际操作次数 kk' 满足 0k500 \leq k' \leq 50
  • 你需要保证你所使用的实际操作次数 SS' 满足 0S6n+100 \leq S' \leq 6n + 10
  • 单个测试点的得分为 $\left(1 - \max(\frac{\max k' - 35}{20}, \max(\frac{S' - 3n - 10}{4n + 1}), 0)\right)\times 30$。
  • Subtask 的得分取所有测试点的得分最小值。

对于所有数据,1V1061 \leq V \leq 10^61n1041 \leq n \leq 10^41T5001 \leq T \leq 500注意由于交互库限制 n,T\bm{n, T} 不会同时取到最大值;此外,对每个子任务 k,Smaxk, S_{\max} 的值已经给出。