这是问题的困难版本。版本之间的差异在于,在此版本中,$$$a_i \leq 10^9$$$。
这是一个运行两次(通信)问题。 在这些问题中,您的程序将运行两次。存储在内存中的所有变量都将在运行之间丢失,但在第一次运行中提供给您的信息对于在第二次运行中正确解决问题可能很重要。因此,主要的挑战是找到一种策略,使用您可以使用的有限输出在两次运行之间进行通信。
时间限制和内存限制是 不 在运行之间共享。例如,在这个问题中,由于时间限制是 $$$2$$$ 秒,因此你只会收到以下判决: 超出时间限制 如果任一运行超过 $$$2$$$ 秒,但如果程序的两次运行都持续 $$$1.5$$$ 秒,则完全没问题。
在这个问题中,你的任务是找到一种策略来编码和解码大小为 $$$n$$$ 的数组 $$$a$$$。
第一次运行是 编码 阶段。陪审团将给您 $$$n$$$ 和 $$$a$$$ 的要素。您的任务是将此数组编码为字符串 $$$s$$$,其中仅包含 小写英文字母,并将 $$$s$$$ 返回给陪审团。然后,您的程序将终止,并且存储在内存中的所有变量都将丢失。
第二次运行是 解码 阶段。陪审团会向您提供字符串 $$$s$$$(与您在第一次运行期间传递给陪审团的字符串相同)。你的任务是解码 $$$s$$$ 并确定陪审团最初给出的 $$$n$$$ 和数组 $$$a$$$ 的元素。换句话说,您必须从第一次运行开始反转您的编码算法。
首次运行
您的代码将在每个测试中运行两次。第一次运行时,您将执行编码。
输入
输入的第一行包含字符串 第一。这样做的目的是让您的程序认识到这是它的第一次运行,并且它应该充当编码算法。
第二行恰好包含一个整数 $$$n$$$ ($$$1 \le n \le 10^4$$$) — $$$a$$$ 的长度。
第三行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。
输出
当准备发送 $$$s$$$ 时,您可以通过打印以下内容来执行此操作:
- $$$s$$$,编码字符串($$$1 \leq |s| \leq 10^5$$$,其中 $$$|s|$$$ 表示 $$$s$$$ 的长度)。该字符串必须仅包含英文字母表中的小写字母,并且打印时不应包含空格。
此后,您的程序应该终止。请注意,存储在内存中的所有变量都将丢失。
第二次运行
在第二次运行时,您将执行解码。
输入
输入的第一行包含字符串 第二。这样做的目的是让您的程序认识到这是它的第二次运行,并且它应该充当解码算法。
输入的第二行包含字符串 $$$s$$$,这是您在第一次运行期间传递给陪审团的变量。
输出
当准备发送 $$$n$$$ 的原始值和数组 $$$a$$$ 时,您可以通过打印以下内容来实现:
- $$$n\, a_1\, a_2\, \ldots\, a_n$$$,原始数组的长度以及数组本身。
示例
输入复制
first 5 100 200 300 400 500
输出复制
skibidi
输入复制
second skibidi
输出复制
5 100 200 300 400 500
注意
这两个例子旨在证明 在同一测试中运行两次.
第一次运行时,陪审团给出 $$$n = 5$$$ 和 $$$a = [100, 200, 300, 400, 500]$$$。读入输入后,您使用编码算法来决定 $$$s$$$ 应该是 斯基比迪。您将其输出回陪审团。然后,您的程序终止,存储在内存中的所有变量都将丢失,第二次运行将继续。
在第二次运行中,陪审团给出 $$$s = \mathtt{skibidi}$$$。读取此输入后,您可以使用解码算法恢复 $$$n$$$ 和 $$$a$$$ 的原始值。幸运的是,您确定 $$$n = 5$$$ 且 $$$a = [100, 200, 300, 400, 500]$$$。您将其输出回陪审团,陪审团检查它是否等于原始值。既然如此,你就会通过这个测试。
这些示例可能无法演示最佳编码/解码算法。