题目描述

Deni 收到了一台非常老的 Pravetz 386 电脑。她想在这台机器上完成一个简单任务：把数组 a_0, a_1, \dots, a_{N-1} 按升序排序。

困难在于，这台电脑的内存极其有限，而且会频繁“重启”。因此，你不能把问题理解成一次普通排序，而是要在多次调用函数的过程中，借助内存单元的读写，逐步完成排序。

你需要实现函数：

bool sort_array(int N, bool start);

系统会反复调用该函数。若本次调用后排序已经完成，则返回 true；否则返回 false，之后还会继续调用。

内存模型

计算机内存被看成编号为 0, 1, \dots, 2N 的单元格。

• 0..N-1：初始数组所在位置；
• N..2N：额外内存；
• 开始时所有额外内存均为 0。

你只能通过以下接口访问这段内存：

unsigned int get_memory(int index);
void set_memory(int index, unsigned int value);

含义如下：

• get_memory(i)：读取第 i 个单元格；
• set_memory(i, x)：将第 i 个单元格改成 x。

你需要实现的函数

bool sort_array(int N, bool start);

• N：数组长度；
• start：第一次调用时为 true，之后均为 false；
• 返回 true 表示排序完成，返回 false 表示尚未完成。

提交要求

你提交的文件必须：

• 文件名为 pravetz.cpp；
• 包含 #include "pravetz.h"；
• 实现 sort_array；
• 不能包含 main；
• 不能读写标准输入输出。

数据范围

• 20 <= N <= 2^16
• 0 <= a_i < 2^16

评分规则

对单个测试，若排序失败，或调用次数超过 10^7，则该测试得分为 0。

否则记：

• gets：在某一次 sort_array 调用中，get_memory 访问到的不同下标数量最大值；
• extra = 1：若整个解法未使用额外内存；
• extra = c：若使用了额外内存，其中 c 由测试所属组决定。

则单测试得分为：

$$\text{score} = extra \times \min\left(1, \frac{num}{gets}\right)$$

Hydro 版配置中，将正式数据按 3 个测试一组 划分成 20 个 5 分分组；每组得分取该组三个测试单测试得分的最小值，再乘以该组分值。

对应参数

• 样例组：c = 0.7, num = 10
• 原子任务 2：c = 0.7, num = 10
• 原子任务 3/4：c = 0.3, num = 3
• 原子任务 5：c = 0.3, num = 4

本地测试（Hydro 配置包）

提供：

• grader.cpp
• pravetz.h

将它们与自己的 pravetz.cpp 一起编译即可。

本地测试输入格式为：

• 第 1 行：N
• 第 2 行：数组 a_0..a_{N-1}
• 第 3 行：测试所属原子任务编号（Hydro 版 grader 会读入但忽略，仅用于与官方数据兼容）

本地 grader 输出格式为：

ok used_extra gets

其中：

• ok = 1 表示排序成功；
• ok = 0 表示排序失败、越界访问或超过调用限制；
• used_extra 表示是否使用额外内存；
• gets 为上文定义的最大不同读取数。