这是问题的困难版本。版本之间的区别在于,在此版本中,所有查询的文章长度总和不得超过 $$$2.5\cdot 10^4$$$。只有解决了该问题的所有版本,您才能破解。
这是一个交互问题。
RiOI 团队最近开发了一款文本编辑器,名为 RiOI编辑器。编辑器仅使用一个整数参数 $$$W$$$ — 每行的宽度。已知 $$$1 \leq W \leq 10^5$$$。
由于您无法理解 RiOI 语言,因此从您的角度来看,单词之间的区别仅在于长度。因此,一个 文章 长度为$$$n$$$的 被定义为由$$$n$$$正整数组成的序列$$$a$$$,其中$$$a_i$$$是$$$i$$$中第$$$i$$$个单词的长度 文章 长度为$$$n$$$的。的 RiOI编辑器 显示 屏幕上的 文章 长度为$$$n$$$的 $$$[a_1, a_2,\ldots, a_n]$$$ 如下:
- 如果 $$$\max(a_1, a_2, \ldots, a_n) \gt W$$$,则编辑器无法显示 文章 长度为$$$n$$$的;
- 否则,编辑器能够显示 文章
长度为$$$n$$$的 通过以下过程:
- 最初,$$$l = 1$$$,$$$s = 0$$$。整个过程中,$$$l$$$始终表示编辑器当前行数,$$$s$$$始终表示最后一行单词长度之和;
- 然后,对于每个 $$$1\le i\le n$$$:
- 如果$$$s + a_i \leq W$$$,则将该单词插入到当前行的末尾。因此,$$$l$$$ 保持不变,$$$s$$$ 增加$$$a_i$$$。
- 否则,该单词将插入新行。因此,$$$l$$$ 变为 $$$l + 1$$$,$$$s$$$ 变为 $$$a_i$$$。
- 显示文章所需的行数是$$$l$$$的最终值。
你对编辑器很感兴趣,所以你决定通过输入一些值来找出$$$W$$$的值 文章 进入编辑器并观察显示每个内容所需的行数 文章 长度为$$$n$$$的.
正式可以向陪审团询问 最多 $$$2$$$ 次。在每个查询中,您输入一个 文章 长度为$$$n$$$的 $$$[a_1, a_2, \ldots, a_n]$$$ ($$$1\leq n \leq 10^5$$$) 给编辑,评审团将回复您:
- 显示所需的行数 文章 长度为$$$n$$$的,如果编辑器能够显示它;
- $$$0$$$,如果编辑器无法显示 文章 长度为$$$n$$$的.
此版本中的附加限制: 的长度总和 所有查询的 文章 (即 $$$n$$$)不得超过 $$$2.5\cdot 10^4$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10$$$)。测试用例的描述如下。
互动
对于每个测试用例,您最多可以进行 $$$2$$$ 查询来找出 $$$W$$$ 的值。保证 $$$1\leq W\leq 10^5$$$。
要进行查询,您应该按以下格式打印新行:
- $$$\texttt{? } n\texttt{ }a_1\texttt{ }a_2\texttt{ }\ldots\texttt{ }a_n$$$ ($$$1 \leq n, a_i \leq 10^5$$$) — 文章 长度为$$$n$$$的 您输入到编辑器。
所有查询的 $$$n$$$ 总和不得超过 $$$2.5\cdot 10^4$$$。
在每个查询结束时,陪审团将打印一个整数,如陈述中所述。
要报告您已找到 $$$W$$$ 的值,请按以下格式打印新行:
- $$$\texttt{! } W$$$ — 编辑器的参数。
打印答案不算作 $$$2$$$ 查询之一。
之后,继续处理下一个测试用例,如果是最后一个测试用例则终止程序。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
这个问题中的交互者是 自适应。这意味着$$$W$$$的值在交互过程中可能会改变,但保证总有至少一个整数$$$W$$$满足所有查询。
黑客
要执行黑客攻击,只有以下格式可用:
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10$$$) — 测试用例的数量。然后,输出一个字符串“手册”在同一行。
每个测试用例的唯一行包含一个整数 $$$W$$$ ($$$1\le W\le 10^5$$$) — 编辑器的参数。
示例的黑客格式如下。
2 manual
20
1
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中; Java 中的
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
2 2 1 0
输出复制
? 5 1 9 4 6 1 ? 2 10 10 ! 20 ? 1 2 ! 1
注意
在第一个测试用例中:
- 对于第一个查询,单词的总长度为$$$1+9+4+6+1=21$$$,并且 文章 长度为$$$n$$$的 分两行显示,因此 $$$W \lt 21$$$;
- 对于第二个查询,单词的总长度为$$$10+10=20$$$,并且 文章 长度为$$$n$$$的 显示在一行中,因此 $$$W\ge 20$$$。
因此,我们确定$$$W = 20$$$。
在第二个测试用例中,编辑器无法显示 文章 长度为$$$n$$$的 中唯一的查询。因此,$$$W \lt 2$$$,所以它只能是$$$1$$$。