本 Hydro 配置包采用 C++17 提交函数题 形式。提交文件中只需要实现指定函数，不要读入、不要输出、不要定义 main 函数。评测程序会调用你实现的函数。

题目背景

在编写安全系统时，需要格外小心，避免攻击者通过程序运行时间推测秘密信息。这类攻击称为计时攻击（timing attack）：程序在不同输入下运行时间可能不同，而在某些情况下，攻击者甚至能通过网络观察这种时间差，从而获取程序处理的秘密数据的信息。

例如，有一个函数用于判断两个字符串是否相等。如果这个函数在发现第一个不同字符时立即返回“不相等”，那么只要能足够精确地测量程序运行时间，攻击者就可能推断出两个字符串第一次不同的位置。

即使程序执行完全相同的指令序列，运行时间也可能因为硬件原因不同。例如，某些现代 AMD 处理器上的 64 位整数除法可能根据被除数和除数的值耗费 10 到 18 个处理器周期。某些很老的处理器上，乘法甚至位移操作的耗时也可能依赖参数值。

还有一种时间差来自处理器缓存。读取缓存中的数据远快于读取主存中的数据。由于一些额外因素，这意味着从内存读取数据的地址也可能被攻击者推断出来。因此，在安全代码中，不允许用“秘密值”作为数组下标。

任务要求

你的任务是用常数时间解决若干经典信息学问题，也就是说：尽量少通过运行时间泄露输入信息。

更准确地说，程序运行时间不应该泄露输入中数值本身的信息；输入规模泄露通常是不可避免的。因此，对于所有规模相同的输入，程序的运行过程应保持一致。

在本题中，我们认为：

• 所有输入值都是秘密值；
• 任何对秘密值进行的算术运算，结果仍然是秘密值；
• 秘密值不能用于 if、while、for 的条件；
• 秘密值不能用于除法和取模；
• 秘密值不能用于数组下标。

本题包含 5 个子任务。你需要在同一个提交文件中实现全部 5 个函数。

secret_int 类型说明

秘密值通过类 secret_int 实现。它大体上像普通无符号整数一样使用，但执行不允许的操作会导致编译错误或评测错误。

secret_int 是 32 位无符号整数，所有算术运算都在模 $2^{32}$ 意义下进行。例如：

0xffffffff + 1 == 0

对 secret_int 进行比较时，返回值仍然是 secret_int，其值为 0 或 1，分别表示比较结果为假或真。

提交方式

你只提交一个 C++ 源文件，实现以下 5 个函数。提交文件中不要写 main 函数，也不要进行标准输入输出。

#include <vector>
#include <tuple>
#include "secret_int.h"

secret_int ith_element(std::vector<secret_int> A, secret_int i);

void sort_arr(std::vector<secret_int>& A);

secret_int connected_components(std::vector<std::vector<secret_int>> A);

std::tuple<secret_int, secret_int, std::vector<secret_int>>
graph_path(std::vector<std::vector<secret_int>> A,
           secret_int B,
           secret_int C);

secret_int is_prime(secret_int N);

注意：C++ 提交中，未完成的函数也不要删除，否则链接时会出错，并且已完成的部分也无法得分。

虽然评测系统尽力安全地实现了 secret_int 的语义，但如果解法试图利用实现细节绕过限制，将不会获得分数。

本地样例评测程序的输入输出格式

样例评测程序会从输入第一行读取两个整数 $S,T$，其中 $S$ 是子任务编号，满足 $0\le S\le 4$；$T$ 是测试次数。

之后依次读取 $T$ 组测试数据。每组数据格式取决于 $S$。对每组数据，评测程序会调用对应的函数，并输出函数返回值。

正式评测时，评测程序不同于样例评测程序，并会检查答案正确性。

---

$S=0$：数组索引

给定长度为 $N$ 的数组 $A$ 和整数 $i$，其中 $0\le i<N$。求 $A[i]$。

需要实现：

secret_int ith_element(std::vector<secret_int> A, secret_int i);

样例评测程序对每组测试读取：

• 第一行两个整数 $N,i$；
• 第二行 $N$ 个整数，表示数组 $A$。

输出函数返回值。

---

$S=1$：数组排序

给定长度为 $N$ 的数组 $A$。请将 $A$ 原地排序为非降序。

需要实现：

void sort_arr(std::vector<secret_int>& A);

该函数直接修改数组 $A$，不需要返回值。

样例评测程序对每组测试读取：

• 第一行一个整数 $N$；
• 第二行 $N$ 个整数，表示数组 $A$。

输出调用函数后的整个数组。

---

$S=2$：无向图连通分量数量

给定一个 $N$ 个顶点的无向图。图以邻接矩阵 $A$ 形式给出：

• 若顶点 $i$ 与 $j$ 之间有边，则 $A[i][j]=1$；
• 否则 $A[i][j]=0$。

保证 $A[i][j]=A[j][i]$ 且 $A[i][i]=0$。

请输出该图的连通分量数量。

需要实现：

secret_int connected_components(std::vector<std::vector<secret_int>> A);

样例评测程序对每组测试读取：

• 第一行一个整数 $N$；
• 接下来 $N$ 行，每行 $N$ 个整数，表示邻接矩阵 $A$。

输出函数返回值。

---

$S=3$：有向图最短路径

给定一个 $N$ 个顶点的带权有向图，顶点编号为 $0$ 到 $N-1$。图以矩阵 $A$ 表示：

• 若 $A[i][j]=0$，表示没有从 $i$ 到 $j$ 的边；
• 否则 $A[i][j]$ 表示边 $i\to j$ 的正整数权值。

保证 $A[i][j] < 2^{32}/N$ 且 $A[i][i]=0$。

另外给定起点 $B$ 和终点 $C$，其中 $0\le B<N$ 且 $0\le C<N$。请找出从 $B$ 到 $C$ 的一条最短路径。保证至少存在一条从 $B$ 到 $C$ 的路径。

需要实现：

std::tuple<secret_int, secret_int, std::vector<secret_int>>
graph_path(std::vector<std::vector<secret_int>> A,
           secret_int B,
           secret_int C);

返回三元组 $(K,L,M)$：

• $K$：路径总权值；
• $L$：路径经过的顶点数量；
• $M$：路径顶点序列。

由于路径长度不能通过数组长度泄露，因此 $M$ 可以比实际路径更长；评测程序只读取 $M$ 的前 $L$ 个元素。

样例评测程序对每组测试读取：

• 第一行三个整数 $N,B,C$；
• 接下来 $N$ 行，每行 $N$ 个整数，表示矩阵 $A$。

输出：

• 第一行输出 $K$；
• 第二行输出 $L$；
• 第三行输出 $M$ 的前 $L$ 个元素。

---

$S=4$：素数判定

给定正整数 $N$，判断 $N$ 是否为素数。若是素数，返回 $1$；否则返回 $0$。

需要实现：

secret_int is_prime(secret_int N);

该子任务中，每个测试中使用 secret_int 进行的操作次数不得超过 $10^6$。

样例评测程序对每组测试读取一个整数 $N$，输出函数返回值。

---

编程示例

下面的例子安全地实现了数组比较。注意这里的循环次数只依赖数组长度，不依赖秘密值本身。

secret_int compare(std::vector<secret_int> a, std::vector<secret_int> b) {
    if (a.size() != b.size()) {
        return 0;
    }
    secret_int result = 1;
    for (int i = 0; i < (int)a.size(); i++) {
        result &= (a[i] == b[i]);
    }
    return result;
}

评分方式

测试点按组评分。只有通过某一组内所有测试，才能获得该组分数。

测试组	分值	限制
0		样例
1	8	$S=0$，$T\le 10$，$N\le 100000$
2	9	$S=1$，$T\le 10$，$N\le 2000$
3	8	$S=1$，$T\le 10$，$N\le 30000$
4	20	$S=2$，$T\le 10$，$N\le 150$
5	25	$S=3$，$T\le 10$，$N\le 100$
6	10	$S=4$，$T\le 500$，$N<10^6$
7	20	$S=4$，$T\le 500$，$N<2^{32}$

样例 1

输入

0 2
3 2
1 2 3
3 0
4294967295 1 2

输出

3
4294967295

说明

本样例包含 2 组测试。第一组中数组为 $[1,2,3]$，询问下标 $2$ 的元素，答案为 $3$。第二组中询问数组 $[4294967295,1,2]$ 的第一个元素，答案为 $4294967295$。

样例 2

输入

1 1
8
3 5 6 5 6 2 5 8

输出

2 3 5 5 5 6 6 8

说明

输出为给定数组排序后的结果。

样例 3

输入

2 1
6
0 0 0 0 0 0
0 0 1 0 0 0
0 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 1
0 0 0 0 1 0

输出

3

说明

图中共有 6 个顶点，3 个连通分量：$\{0\}$、$\{1,2\}$ 和 $\{3,4,5\}$。

样例 4

输入

3 1
4 0 3
0 3 0 9
0 0 2 4
0 2 0 3
0 0 0 0

输出

7
3
0 1 3

说明

从顶点 $0$ 到顶点 $3$ 的最短路径是 $0\to 1\to 3$，总权值为 $3+4=7$，经过 3 个顶点。

样例 5

输入

4 2
4
11

输出

0
1

说明

第一组测试中 $4$ 不是素数，返回 $0$；第二组测试中 $11$ 是素数，返回 $1$。