题目类型说明

这是一道提交函数题。

你需要提交一个源文件，实现指定函数；评测时你的程序会与评测器一同编译运行。
不要实现 main 函数，不要从标准输入读入，也不要向标准输出输出。

你需要包含头文件：

#include "ops.h"

---

题目描述

Alice 经常需要对包含 N 个数的序列进行排序，她已经厌烦了手动完成这件事。于是她买了一台能够替她排序数字的机器，但这台机器的功能非常受限，Alice 也不确定该如何正确使用它。

这台机器有 M = 10^5 个寄存器，编号为 0 到 M - 1。每个寄存器都是 8 位的，也就是说其值始终在 0 到 255 之间。

机器不能进行输入或输出，只能对寄存器执行操作。一次操作由 4 个参数给出：

• In1
• In2
• Out
• Table

其中：

• In1、In2 和 Out 是寄存器编号（允许其中若干个编号相同）；
• Table 是一个 256 × 256 的表，表中每个值都在 0 到 255 之间。

执行该操作时，机器按如下步骤进行：

1. 读取寄存器 In1 和 In2 的值，分别记为 V1 和 V2；
2. 计算 U = Table[V1][V2]；
3. 将结果 U 写入寄存器 Out。

也就是说，若记寄存器 i 中的值为 R_i，则该操作等价于：

$$R_{\text{Out}} := \text{Table}_{R_{\text{In1}}, R_{\text{In2}}}$$

不过，这台机器只有一个操作头，而且它的可达范围非常有限。因此三个寄存器的位置必须彼此接近。更准确地说，任意两者下标之差的绝对值都不能超过 D = 26：

$$\max\left(|\text{In1}-\text{In2}|,\ |\text{In1}-\text{Out}|,\ |\text{In2}-\text{Out}|\right)\le 26$$

Alice 要排序的序列为 A_0, A_1, ..., A_{N-1}，并且所有数都不超过 10^{18}。她注意到，一个数最多只需要 60 位，因此可以用 8 个寄存器存储一个数（因为 8 × 8 = 64 ≥ 60）。

由于机器不能输入，测试开始前会直接把输入数据写入机器内存，而所有其他寄存器会被填入任意值。类似地，由于机器也不能输出，最后会直接从机器内存中读取输出数据，而其余寄存器中的值会被忽略。

输入和输出的格式都是“若干个数的列表”（设数量为 K）：

• 这些数会写入 / 读出前 8K 个寄存器；
• 第 P 个数占用寄存器 8P 到 8P + 7；
• 每个数按 256 进制、从低位到高位 存储。

也就是说，若第 P 个数为 X，则有：

$$X=\sum_{i=0}^{7} 256^i \cdot R_{8P+i}$$

更具体地：

• 输入时，Alice 把十进制数转换为 256 进制后写入对应寄存器；
• 输出时，她从对应寄存器读取这些“256 进制位”，并将其还原为通常使用的整数。

在本题中，Alice 要对 N 个数进行非降序排序。输入由数字 N 和随后这 N 个数构成：

$$A_0, A_1, ..., A_{N-1}$$

因此：

• 输入会写入前 8(N+1) 个寄存器；
• 其中前 8 个寄存器保存 N；
• 后面的寄存器依次保存 A_0, A_1, ..., A_{N-1}；
• 所有剩余寄存器中的值都是任意的。

注意：为了统一格式，N 也用 8 个寄存器存储，尽管它本可以用更少的寄存器表示。

例如，若：

• N = 3
• A_0 = 25655
• A_1 = 500
• A_2 = 1966081

则前 32 个寄存器的值为：

3, 0, 0, 0, 0, 0, 0, 0,
55, 100, 0, 0, 0, 0, 0, 0,
244, 1, 0, 0, 0, 0, 0, 0,
1, 0, 30, 0, 0, 0, 0, 0

输出应当是排好序后的 N 个数 A_0, A_1, ..., A_{N-1}，即只读取前 8N 个寄存器即可；其余寄存器中的值会被忽略。在上面的例子中，输出对应的前 24 个寄存器应为：

244, 1, 0, 0, 0, 0, 0, 0,
55, 100, 0, 0, 0, 0, 0, 0,
1, 0, 30, 0, 0, 0, 0, 0

你的任务是向机器发送一系列操作，使得它最终把这 N 个数按非降序排列。
Alice 很忙，因此希望排序尽可能快完成，也就是说，你应尽量减少操作次数。

---

实现要求

你需要实现函数：

void sortNumbers(int maxN)

该函数会被调用恰好一次。参数 maxN 是该测试中 N 的上界，即：

$$N \le \text{maxN}$$

注意：你的程序不知道具体的 N，因为它只被写在前 8 个寄存器中。

你可以调用由评测器提供的函数：

void applyOp(
    int input1,
    int input2,
    int output,
    const std::array<std::array<int, 256>, 256>& opTable
)

它会执行一条上述定义的操作。

注意 opTable 的类型：这是一个尺寸固定为 256 × 256 的二维数组类型；与普通的 int opTable[256][256] 相比，这种写法能让编译器检查维度是否正确。

你的程序将与评测器一起编译。
不要实现 main 函数，不要读写标准输入输出。
你必须包含头文件 ops.h。题目会提供本地评测器和头文件，便于你本地测试。

在正式评测中，评测器会在同一个测试内，对你的操作序列作用于 T 个子测试；只有当你的操作序列在所有这些子测试上都能正确完成排序，该测试才算通过。注意，这并不意味着 sortNumbers 会被调用 T 次——它仍然只会被调用一次。

---

限制

• 1 ≤ N ≤ maxN ≤ 350
• 0 ≤ A_i ≤ 10^{18}
• M = 10^5
• D = 26
• T ≤ 30

---

子任务

子任务	分值	maxN	其他限制
1	10	= 2	N = maxN，A_i ≤ 200
2	9		N = maxN
3	11	≤ 150
4			无
5	38	≤ 350	N = maxN
6	21		无

给定子任务的分数，只有在该子任务及其包含的所有更弱限制子任务全部通过时才能获得。

---

评分方式

你在某个子任务上的得分，等于该子任务中所有测试点得分的最小值。

设：

• C 为你的程序向机器发送的操作次数；
• G = 2150000 为目标操作数。

则单个测试点得分 S 定义为：

• 若 C ≤ G，则 S = 1
• 若 C ≥ 3G，则 S = 0
• 否则：

$$S = \left(1 - 0.5 \times \left(\frac{C}{G} - 1\right)\right)^{2.25}$$