QOJ.ac

QOJ

Total points: 100 Interactive Unavailable

# 5366. 面国超算

统计

面皇有 $n$ 台电脑,这 $n$ 台电脑两两之间都用了特殊的缆线连接,它们的编号是 $0 \cdots n-1$。

现在有两个 $n \times n$ 的元素都是 $32$ 位无符号整数的矩阵 $A[0\cdots n-1, 0\cdots n-1]$,$B[0\cdots n-1, 0\cdots n-1]$。你需要用这些电脑来计算矩阵 $C=AB$。你只需要计算 $C$ 中每个元素对 $2^{32}$ 取模的结果。

一开始第 $i$ 台电脑只知道 $A$ 的第 $i$ 行的值和 $B$ 的第 $i$ 行的值,你需要让他们进行一些计算,使得最终第 $i$ 台电脑知道 $C$ 的第 $i$ 行的值。你需要让这些电脑进行通信来完成计算。

通信是分轮次进行的。具体来说,每一轮开始的时候,对于每个 $i$,第 $i$ 台电脑会根据已知的信息决策出一个数组 $\{\mathrm{sendTo}_{i,j}, 0 \leq j < n\}$,表示本轮第 $i$ 台电脑将给第 $j$ 台电脑发送什么信息。当所有电脑都完成决策后,所有 $\mathrm{sendTo}_{i,j}$ 都会瞬间传送到他的目标电脑上。在传输完成以后,这 $n$ 台电脑就会进入下一轮通信。(注意:和试机赛题目不同的是,这里同一台电脑发送给其他电脑的信息不一定要相同)。

由于缆线十分特殊,带宽相当有限(其实是因为面黄拨的经费太少)。因此,每轮通信中,$\mathrm{snedTo}_{i,j}$ 只能传输 $32$ 个二进制位。也就是说,$\mathrm{sendTo}_{i,j}$ 必须是 $0$ 至 $2^{32}-1$ 内的一个 $32$ 位无符号整数。

同时,每台电脑的磁盘大小也十分有限(也是因为经费太少),里面只能存储 $4 \times 10^{4}$ 个 $32$ 位二进制数。

现在你需要设计一个合理的算法,使得在尽量少的轮数内(经费太少不够付电费),每台电脑能计算出自己要计算的东西。

以上是题目北京,由于评测系统的限制,我们将通过一些手段来模拟通信的过程。下面将介绍模拟的方法。

在本题中,你需要实现函数

void node_mul(int maxSize, int node_id, int round_id);

其中 node_id 表示当前电脑的编号,round_id 表示当前是第几轮通信,通信的轮数从 $1$ 开始计数。

接下来我们用 uint 表示 $32$ 位无符号整数。

我们设置了一个全局变量 CO,你的代码需要和它交互来完成计算。

CO 记录了整个通信过程中的传输的信息,每台电脑初始得到的信息和每台电脑的存储系统。我们将第 $i$ 台电脑中存储的 $4 \times 10^4$ 个 $32$ 位二进制数组织成一个数组 uint F[i][40000] 供我们存取。

CO 有下面这些方法可以调用:

  • uint getMemory(int w)
    • 返回 F[node_id][w]
  • void updateMemory(int w, uint val)
    • F[node_id][w] 修改为 val
  • uint getinfoA(int w)
    • 返回 A[node_id][w]
  • uint getinfoB(int w)
    • 返回 B[node_id][w]
  • uint getinfoT(int k, int w)
    • 获取当前电脑在第 $k$ 轮种收到的来自第 $w$ 台电脑的消息,要求 $1 \leq k < \mathrm{round_id}$。
  • void updateC(int w, uint val)
    • 提交 val 作为 C[node_id][w] 的答案,你可以多次提交,只会采用最后一次。
  • void getinfoC(int w)
    • 返回你提交过的 C[node_id][w],如果你没有提交过,则返回 $0$。
  • void sendinfoTo(int k, uint w)
    • 在本轮通信中,这台电脑要发送 $w$ 给第 $k$ 台电脑,你可以在同一轮同一台电脑上多次调用该函数发送给同一台电脑,但是我们只采用最后一次。

例如你在 node_mul(5, 2, 2) 中先后调用了:

CO.sendinfoTo(1, 2);
CO.sendinfoTo(1, 3);

则我们视为你向电脑 $1$ 发送了信息 $3$。

下面介绍我们的模拟方法。

我们会先枚举 $i=1\cdots 130$,表示当前通信的轮数,接着在循环体内部枚举 $j=0\cdots n-1$,调用 node_mul(matSize, j, i),之后检查是否所有的电脑已经提交了正确的答案,即是否对所有 $x$,第 $x$ 台电脑已经知道了 $C$ 中第 $x$ 行的所有元素。如果是的话,结束测试,我们认为这些电脑用了 $i$ 轮完成了计算。若 $130$ 轮通信结束后,仍然存在一台电脑没有计算出自己应该计算的东西,则被视为使用了 $131$ 轮通信完成了计算。

以下是一些代码规范和注意事项。

在函数 node_mul 中,任何非法传递信息的行为,即不通过题目中给定的方法来传递信息的行为,都会被认为是作弊,它们包括但不限于:开全局变量;内嵌汇编代码;使用 malloccalloc 等函数开辟内存,通过 new 指针来共享内存;将数据写到本地磁盘上等。

同时,你不允许调用除了 CO 的方法以外的任何函数,不能定义任何全局变量,包括静态全局变量。

除此以外,如果你在调用 CO 的方法的时候传入的参数不合法(比如 getMemory(-1)sendinfoTo(114514, 35)),那么模拟器会陷入死循环并使你的代码超时。

另外,由于我们使用的是代码填空机制,你只能在代码空格处填写上 node_mul 函数的实现,不能有违规操作,包括但不限于:将 node_mul 函数提前结束并声明其他函数等。

最后,某些企图修改内存的行为也是不合法的,你不能够修稿我们定义的每一个全局变量的值,比如修改 CO 类型体里面每一个变量的值。

我们会人工检查你的代码是否使用了违规的行为,如果我们认为你的代码有违规行为(包括但不仅限于以上提到的行为),那么我们会拒绝你的提交,把你本次的提交的分数变成 $0$ 分并通知你。由于人工检查有一定延迟,请尽量避免比赛结束前几分钟提交一些危险代码,不然可能会导致比赛结束后才知道提交被拒绝。

但是,你可以在函数体内声明一些局部变量和数组来帮助你完成计算。

你可以查看我们下发的 see.cpp 来了解其他细节,但是 see.cpp 并不是我们最后测试用的代码,最后测试用的代码将会进行一些加密。最后测试时,我们将会把你的代码填进 see.cpp,然后运行,如果 see.cpp 运行超过了 $50$ 秒,则你本题算超时。

提交时请提交函数体内的代码,假如你补全成了 void node_mul(int matSize, int node_id, int round_id){int yjq;},提交时应该只提交 “ int yjq; ”。

注意,在本地测试 see.cpp 时,你需要将栈大小开大。

数据规模与约定

本题只有一个测试点 $n = 125$。

假设你花 $x$ 轮完成了计算,那么你最后得到的分数是

$$f(x) = \begin{cases} 0 & x \geq 126 \\ 100 & x \leq 34 \\ \max\left(20, \min\left(100, \left( 100, \left\lfloor60 + 10 \times \ln\left(\frac{y}{1-y}\right)\right\rfloor \right)\right)\right) & \text{否则}\end{cases}$$

其中 $y=\displaystyle \frac{80-x}{92}+0.5$,这个除法没有取整。


或者逐个上传: