33OJ
登录 注册

#P15991. [PA 2026] 矩阵编码 / Kodowanie macierzami

    ID: 20125 远端评测题 10000ms 1024MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>交互题Special Judge2026通信题PA(波兰)

[PA 2026] 矩阵编码 / Kodowanie macierzami

题目描述

Algosia 和 Bajtek 非常忙碌。他们没有时间想出原创的题目,更没有时间互相发送 1000×10001000 \times 1000 大小的矩阵——而这正是他们参加今年信息学奥林匹克决赛时不得不做的事情。

Algosia 想要将某个正整数传递给 Bajtek。不幸的是,正如他们最近常遇到的情况一样,隔在他们之间的是一套非常先进的计算机系统。Algosia 可以向计算机输入一个 10×1010 \times 10 的二进制矩阵,随后系统会对该矩阵的行和列进行置换,并将其发送给 Bajtek。请编写一个程序,帮助 Algosia 和 Bajtek 进行 tt 次数字的编码与解码。

实现细节

这是一道通信题。你的程序将以两个副本运行——一个代表 Algosia,另一个代表 Bajtek。每次运行在输入的第一行会收到单词 Algosia 或 Bajtek,用以指明该副本负责哪一方的行为。

两个程序在收到各自的单词后,还会立即在输入中获得两个整数 nn 和 tt(1≤n≤3⋅10161 \le n \le 3 \cdot 10^{16},1≤t≤251 \le t \le 25),分别表示被编码数字的上限以及测试用例的数量。随后进行 tt 次交互。

在第 ii 次交互开始时,Algosia 收到一个整数 nin_i(1≤ni≤n1 \le n_i \le n)。她应在输出中打印 10 行,每行包含 10 个字符。每个字符应等于 0 或 1。该矩阵的行和列将被置换后,以相同格式发送至 Bajtek 进程的输入。Bajtek 进程在收到矩阵后,应在输出中打印出 Algosia 所编码的数字 nin_i。打印该数字后,下一个测试用例开始。

每次输出片段后,必须刷新输出缓冲区,例如通过调用 cout.flush() 或 fflush(stdout)。

注意事项

  • 下面描述的交互对应名为 kod0a.in 的第一个示例测试。
  • 两个程序同时启动。程序的运行时间以交互器从启动到结束的实际时间来计量。
  • Algosia 只有在 Bajtek 解码出上一个数字之后,才会收到下一个数字。
  • Bajtek 的进程在读取 nn 和 tt 之后,无需阻塞等待输入,可以利用 Algosia 进程编码第一个数字期间的时间进行任意计算。在极端情况下,这可以使程序速度提升至两倍。

输入格式

见「实现细节」。

输出格式

见「实现细节」。

提示

示例交互

交互器 → Algosia Algosia → 交互器 交互器 → Bajtek Bajtek → 交互器 说明
Algosia Bajtek 交互器告知 Algosia 和 Bajtek 的程序副本各自的身份。
2020 22 2020 22 双方得知将有两个测试用例,且每个用例中待传递的最大数字不超过 2020。
1212 Algosia 收到待编码的数字 1212。
$\texttt{1110000000}\\\texttt{1000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}$ Algosia 发送编码数字 1212 的矩阵。
$\texttt{0000000000}\\\texttt{0000100000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0100100001}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}$ Bajtek 收到列和行被置换后的矩阵。
1212 Bajtek 报告从矩阵中解码出数字 1212。
1111 Algosia 收到待编码的数字 1111。
$\texttt{1110000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}$ Algosia 发送编码数字 1111 的矩阵。
$\texttt{0000000100}\\\texttt{0000000100}\\\texttt{1000000101}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}$ Bajtek 收到列和行被置换(可能与之前方式不同)后的矩阵。
1111 Bajtek 报告从矩阵中解码出数字 1111。

评分

测试数据集由 1010 组组成,每组可得 00 或 11 分。各组对 nn 值的限制如下:

组号 n≤n \le
1 101010^{10}
2 101110^{11}
3 101210^{12}
4 101310^{13}
5 101410^{14}
6 101510^{15}
7 5⋅10155 \cdot 10^{15}
8 101610^{16}
9 2⋅10162 \cdot 10^{16}
10 3⋅10163 \cdot 10^{16}

本地测试

在"文件"部分提供了交互器 kodsoc.cpp。文件中提供的交互器在发送给 Bajtek 之前不会对矩阵进行置换;除此区别外,它与 SIO 上评测提交所用的交互器对选手程序进行完全相同的交互。运行命令如下:

python3 kodrun.py [解答] < [测试]

其中 kodsoc.cpp 和 o1.h 必须位于同一文件夹中。交互器接受的输入格式在 kodsoc.cpp 文件的注释中有所描述。可通过运行命令 python3 kodrun.py -h 了解 kodrun.py 脚本的其他选项。

公平竞赛规则

禁止通过交互流程以外的方式在两个程序之间进行通信,例如通过一个程序延迟发送动作并由另一个程序读取时钟。如果评委发现程序之间存在非法通信的尝试,该提交可能被取消,情节严重者可能被取消参赛者在整个比赛中的资格。