luogu#P9918. 「RiOI-03」Just a Q. (Hard ver.)
「RiOI-03」Just a Q. (Hard ver.)
题目背景
「Yes, I am Q.」
面前的小 R 莞尔一笑。
- 保证本题的任何合理的部分分或正解的 std + spj 均可以在当前数据下, ms 的时间限制、 MB 的空间限制内正确运行并获得 AC 状态。
- 本题不添加仅为无意义地卡满 spj 运行时间的 hack 数据。
请注意,本题只有约束范围与普通版不同,且两个版本的约束范围并不完全重叠。
题目描述
这是一道交互题。
小 R 有一个变量 。 初始为 。
小 R 有 个隐藏的整数 ,满足 ,且有且仅有一个 满足 ,而面前的你,需要得出这个满足 的下标 。
小 R 承诺不会让你以仅仅 的几率盲猜,所以她可以允许你进行最多 次询问。每次询问,你可以向小 R 给出可重正整数集合 满足 且 ,她会计算 ,然后让 。特殊地,若 为空集,则 。
一次询问后,小 R 会向你给出此时的 (为 +
,-
或 0
),表示 的符号。具体地,若 ,小 R 返回 +
;若 ,小 R 返回 -
;否则返回 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
,表示当前 的符号 。
输入格式
本题有多组数据。
第一行,一个整数 表示数据组数。
对于每一组数据,请按照 【交互格式】 进行交互。当你报告下标后:
- 如果你给出的下标正确:
- 如果这是最后一组数据,交互库退出并返回 Accepted;
- 如果这不是最后一组数据,你应当接着读入 以进行下一组数据的交互。
- 否则,下标错误,交互库会立刻终止,返回 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
。
数据规模与约定
本题采用捆绑测试。
子任务编号 | 分值 | ||||
---|---|---|---|---|---|
对于子任务 ,若通过所有测试点则获得全部分数,否则获得 分。
对于子任务 :
- 你需要保证你所使用的实际操作次数 满足 。
- 你需要保证你所使用的实际操作次数 满足 。
- 单个测试点的得分为 $\left(1 - \max(\frac{\max k' - 35}{20}, \max(\frac{S' - 3n - 10}{4n + 1}), 0)\right)\times 30$。
- Subtask 的得分取所有测试点的得分最小值。
对于所有数据,,,,注意由于交互库限制 不会同时取到最大值;此外,对每个子任务 的值已经给出。