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$,这个除法没有取整。


或者逐个上传:
About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

  1. This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
  2. Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
  3. Issues must be filed in English or Chinese only.
  4. Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0

No issues in this category.