雅妮是一个鸟类爱好者。自从读了关于 IP over Avian Carriers (IPoAC) 的文章后，她花了很多时间训练一群聪明的鹦鹉来传递长距离的信息。

雅妮的梦想是利用她的鸟将一条消息 $M$ 传送到遥远的地方。她的消息 $M$ 是一个由 $N$ 个整数（不一定两两不同）组成的序列，每个整数都在 $0$ 到 $255$ 之间（包含边界）。雅妮有 $K$ 只经过特殊训练的鹦鹉。所有的鹦鹉看起来都一模一样，雅妮无法区分它们。每只鸟可以记住一个介于 $0$ 到 $R$ 之间（包含边界）的整数。

起初，她尝试了一个简单的方案：为了发送消息，雅妮小心翼翼地把鸟一只一只地放出口袋。在每只鸟飞上天空之前，她按顺序教它消息序列中的一个数字。不幸的是，这个方案行不通。最终，所有的鸟确实都到达了目的地，但它们到达的顺序不一定与它们离开时的顺序相同。通过这个方案，雅妮可以找回她发送的所有数字，但她无法将它们按正确的顺序排列。

为了实现她的梦想，雅妮需要一个更好的方案，为此她需要你的帮助。给定一条消息 $M$，她计划像以前一样把鸟一只一只地放出去。她需要你编写一个程序来执行两个独立的操作：

• 首先，你的程序应该能够读取消息 $M$，并将其转换为一个由最多 $K$ 个介于 $0$ 到 $R$ 之间的整数组成的序列，她将用这些数字来教导这些鸟。
• 其次，你的程序应该能够读取鸟类到达目的地时接收到的介于 $0$ 到 $R$ 之间的整数列表，然后将其转换回原始消息 $M$。

你可以假设所有的鹦鹉总是能到达目的地，并且它们中的每一只都记住了分配给它的数字。雅妮再次提醒你，鹦鹉可能会以任意顺序到达。请注意，雅妮只有 $K$ 只鹦鹉，因此你生成的介于 $0$ 到 $R$ 之间的整数序列必须包含最多 $K$ 个整数。

任务描述

编写两个独立的函数（过程）。其中一个将由发送方（编码器）使用，另一个由接收方（解码器）使用。

整体流程如下图所示：

整体流程示意图

你需要编写的两个函数是：

• 函数 encode(N, M)，它接受以下参数：

  • N – 消息的长度。
  • M – 一个包含 $N$ 个整数的一维数组，表示消息。你可以假设对于 $0 \le i < N$，有 $0 \le M[i] \le 255$。

  该函数必须将消息 $M$ 编码为一个介于 $0$ 到 $R$ 之间（包含边界）的整数序列，该序列将使用鹦鹉发送。为了报告这个序列，你的 encode 函数必须对你希望给其中一只鸟的每个整数 $a$ 调用一次 send(a) 函数。

• 函数 decode(N, L, X)，它接受以下参数：

  • N – 原始消息的长度。
  • L – 接收到的消息长度（即发送的鸟的数量）。
  • X – 一个包含 $L$ 个整数的一维数组，表示接收到的数字。对于 $0 \le i < L$ 的数字 $X[i]$ 正是你的 encode 函数生成的数字，但可能被重新排列成了不同的顺序。

  该函数必须恢复原始消息。为了报告它，你的 decode 函数必须对解码后消息中的每个整数 $b$ 按正确的顺序调用一次 output(b) 函数。

请注意，$R$ 和 $K$ 没有作为输入参数给出——请参阅下面的子任务描述。

为了正确解决给定的子任务，你的函数必须满足以下条件：

• 你的 encode 函数发送的所有整数必须在子任务指定的范围内。
• 你的 encode 函数调用 send 函数的次数不能超过子任务中指定的限制 $K$。请注意，$K$ 取决于消息的长度。
• decode 函数必须正确恢复原始消息 $M$，并恰好调用 output(b) 函数 $N$ 次，其中 $b$ 依次等于 $M[0], M[1], \dots, M[N-1]$。

在最后一个子任务中，你的得分将根据编码后消息的长度与原始消息长度的比值而变化。

样例

样例输入 1

N = 3
M = [10, 30, 20]

样例输出 1

[10, 30, 20]

说明

函数 encode(N, M) 使用某种奇特的方法，可能会将消息编码为数字序列 $(7, 3, 2, 70, 15, 20, 3)$。为了报告这个序列，它应该按如下方式调用 send 函数：

send(7)
send(3)
send(2)
send(70)
send(15)
send(20)
send(3)

一旦所有鹦鹉到达目的地，假设我们获得了以下抄录的数字列表：$(3, 20, 70, 15, 2, 3, 7)$。然后将调用 decode 函数，其中 $N=3, L=7$，且 $X = [3, 20, 70, 15, 2, 3, 7]$。

函数 decode 必须产生原始消息 $(10, 30, 20)$。它通过按如下方式调用 output 函数来报告结果：

output(10)
output(30)
output(20)

子任务

子任务 1 (17 分)

• $N = 8$，且数组 $M$ 中的每个整数均为 $0$ 或 $1$。
• 每个编码后的整数必须在 $0$ 到 $R=65535$ 的范围内（包含边界）。
• 你可以调用 send 函数的次数最多为 $K=10 \times N$。

子任务 2 (17 分)

• $1 \le N \le 16$。
• 每个编码后的整数必须在 $0$ 到 $R=65535$ 的范围内（包含边界）。
• 你可以调用 send 函数的次数最多为 $K=10 \times N$。

子任务 3 (18 分)

• $1 \le N \le 16$。
• 每个编码后的整数必须在 $0$ 到 $R=255$ 的范围内（包含边界）。
• 你可以调用 send 函数的次数最多为 $K=10 \times N$。

子任务 4 (29 分)

• $1 \le N \le 32$。
• 每个编码后的整数必须在 $0$ 到 $R=255$ 的范围内（包含边界）。
• 你可以调用 send 函数的次数最多为 $K=10 \times N$。

子任务 5 (最多 19 分)

• $16 \le N \le 64$。
• 每个编码后的整数必须在 $0$ 到 $R=255$ 的范围内（包含边界）。
• 你可以调用 send 函数的次数最多为 $K=15 \times N$。
• 重要提示：此子任务的得分取决于编码后消息的长度与原始消息长度的比值。

对于该子任务中的给定测试用例 $t$，设 $P_t = L_t / N_t$ 为编码后消息长度 $L_t$ 与原始消息长度 $N_t$ 的比值。设 $P$ 为所有 $P_t$ 的最大值。你在此子任务中的得分将根据以下规则确定：

• 如果 $P \le 5$，你将获得该子任务的满分 $19$ 分。
• 如果 $5 < P \le 6$，你将获得 $18$ 分。
• 如果 $6 < P \le 7$，你将获得 $17$ 分。
• 如果 $7 < P \le 15$，你的得分将为 $1 + 2 \times (15 - P)$，向下取整到最接近的整数。
• 如果 $P > 15$ 或你的任何输出不正确，你的得分为 $0$ 分。

重要提示：任何适用于子任务 1 到 4 的有效解法也将解决所有先前的子任务。然而，由于对 $K$ 的限制较大，子任务 5 的有效解法可能无法解决子任务 1 到 4。你可以使用同一种解法来解决所有子任务。

实现细节

数据范围

• 评测环境：在实际评测环境中，你提交的代码将被编译为两个单独执行的程序 e 和 d。你的编码器和解码器模块将分别链接到每个可执行文件中，但 e 只会调用 encode，而 d 只会调用 decode。
• CPU 时间限制：程序 e 将对函数 encode 进行 50 次调用，且应在 2 秒内运行完毕。程序 d 将对函数 decode 进行 50 次调用，且应在 2 秒内运行完毕。
• 内存限制：256 MB。
• 注意：对栈空间大小没有显式限制。栈内存计入总内存使用量。

接口 (API)

• 实现文件夹：parrots/

• 需由选手实现的文件：

  • encoder.c 或 encoder.cpp 或 encoder.pas
  • decoder.c 或 decoder.cpp 或 decoder.pas

C/C++ 程序员注意事项：在样例评测程序和实际评测程序中，encoder.c[pp] 和 decoder.c[pp] 都会与评测程序链接在一起。因此，你应该在每个文件中将所有全局变量声明为 static，以防止它们与其他文件中的变量发生冲突。

• 选手接口：

  • encoder.h 或 encoder.pas
  • decoder.h 或 decoder.pas

• 评测程序接口：

  • encoderlib.h 或 encoderlib.pas
  • decoderlib.h 或 decoderlib.pas

• 样例评测程序：grader.c 或 grader.cpp 或 grader.pas

样例评测程序执行两个独立的轮次。在每一轮中，它首先使用给定的数据调用 encode，然后使用你的 encode 函数生成的输出调用 decode。在第一轮中，评测程序不会改变编码后消息中整数的顺序。在第二轮中，样例评测程序会交换奇数和偶数位置上的整数。实际评测程序将对编码后的消息应用各种排列。你可以通过修改其 shuffle 函数（C/C++ 中）或 Shuffle 过程（Pascal 中）来改变样例评测程序打乱数据的方式。

样例评测程序还会检查编码后数据的范围和长度。默认情况下，它检查编码后的数据是否在 $0$ 到 $65535$ 之间（包含边界），以及长度是否最多为 $10 \times N$。你可以通过调整常量 channel_range（例如从 $65535$ 改为 $255$）和 max_expansion（例如从 $10$ 改为 $15$ 或 $7$）来改变这些检查。

• 样例评测程序输入：grader.in.1, grader.in.2, ...

注意：样例评测程序按以下格式读取输入：

• 第 1 行：$N$

• 第 2 行：$N$ 个数字的列表：$M[0], M[1], \dots, M[N-1]$

• 样例评测程序输入的期望输出：grader.expect.1, grader.expect.2, ... 对于本任务，这些文件中的每一个都应精确包含文本 "Correct."。