P15991 [PA 2026] 矩阵编码 / Kodowanie macierzami
题目描述
Algosia 和 Bajtek 非常忙碌。他们没有时间想出原创的题目，更没有时间互相发送 $1000 \times 1000$ 大小的矩阵——而这正是他们参加今年信息学奥林匹克决赛时不得不做的事情。
Algosia 想要将某个正整数传递给 Bajtek。不幸的是，正如他们最近常遇到的情况一样，隔在他们之间的是一套非常先进的计算机系统。Algosia 可以向计算机输入一个 $10 \times 10$ 的二进制矩阵，随后系统会对该矩阵的行和列进行置换，并将其发送给 Bajtek。请编写一个程序，帮助 Algosia 和 Bajtek 进行 $t$ 次数字的编码与解码。
### 实现细节
**这是一道通信题**。你的程序将以两个副本运行——一个代表 Algosia，另一个代表 Bajtek。每次运行在输入的第一行会收到单词 Algosia 或 Bajtek，用以指明该副本负责哪一方的行为。
两个程序在收到各自的单词后，还会立即在输入中获得两个整数 $n$ 和 $t$（$1 \le n \le 3 \cdot 10^{16}$，$1 \le t \le 25$），分别表示被编码数字的上限以及测试用例的数量。随后进行 $t$ 次交互。
在第 $i$ 次交互开始时，Algosia 收到一个整数 $n_i$（$1 \le n_i \le n$）。她应在输出中打印 10 行，每行包含 10 个字符。每个字符应等于 0 或 1。该矩阵的行和列将被置换后，以相同格式发送至 Bajtek 进程的输入。Bajtek 进程在收到矩阵后，应在输出中打印出 Algosia 所编码的数字 $n_i$。打印该数字后，下一个测试用例开始。
**每次输出片段后，必须刷新输出缓冲区，例如通过调用 `cout.flush()` 或 `fflush(stdout)`。**
### 注意事项
- 下面描述的交互对应名为 kod0a.in 的第一个示例测试。
- 两个程序同时启动。程序的运行时间以交互器从启动到结束的实际时间来计量。
- Algosia 只有在 Bajtek 解码出上一个数字之后，才会收到下一个数字。
- Bajtek 的进程在读取 $n$ 和 $t$ 之后，无需阻塞等待输入，可以利用 Algosia 进程编码第一个数字期间的时间进行任意计算。在极端情况下，这可以使程序速度提升至两倍。
输入格式
见「实现细节」。
输出格式
见「实现细节」。
说明/提示
### 示例交互
| 交互器 → Algosia | Algosia → 交互器 | 交互器 → Bajtek | Bajtek → 交互器 | 说明 |
|:---|:---|:---|:---|:---|
| Algosia | | Bajtek | | 交互器告知 Algosia 和 Bajtek 的程序副本各自的身份。 |
| $20$ $2$ | | $20$ $2$ | | 双方得知将有两个测试用例，且每个用例中待传递的最大数字不超过 $20$。 |
| $12$ | | | | Algosia 收到待编码的数字 $12$。 |
| | $\texttt{1110000000}\\\texttt{1000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}$ | | | Algosia 发送编码数字 $12$ 的矩阵。 |
| | | $\texttt{0000000000}\\\texttt{0000100000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0100100001}\\\texttt{0000000000}\\\texttt{0000000000}\\\texttt{0000000000}$ | | Bajtek 收到列和行被置换后的矩阵。 |
| | | | $12$ | Bajtek 报告从矩阵中解码出数字 $12$。 |
| $11$ | | | | Algosia 收到待编码的数字 $11$。 |
| | $\texttt{1110000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}\\\texttt{1000000000}$ | | | Algosia 发送编码数字 $11$ 的矩阵。 |
| | | $\texttt{0000000100}\\\texttt{0000000100}\\\texttt{1000000101}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}\\\texttt{0000000100}$ | | Bajtek 收到列和行被置换（可能与之前方式不同）后的矩阵。 |
| | | | $11$ | Bajtek 报告从矩阵中解码出数字 $11$。 |
### 评分
测试数据集由 $10$ 组组成，每组可得 $0$ 或 $1$ 分。各组对 $n$ 值的限制如下：
| 组号 | $n \le$ |
|------|---------|
| 1 | $10^{10}$ |
| 2 | $10^{11}$ |
| 3 | $10^{12}$ |
| 4 | $10^{13}$ |
| 5 | $10^{14}$ |
| 6 | $10^{15}$ |
| 7 | $5 \cdot 10^{15}$ |
| 8 | $10^{16}$ |
| 9 | $2 \cdot 10^{16}$ |
| 10 | $3 \cdot 10^{16}$ |
### 本地测试
在"文件"部分提供了交互器 kodsoc.cpp。文件中提供的交互器在发送给 Bajtek 之前不会对矩阵进行置换；除此区别外，它与 SIO 上评测提交所用的交互器对选手程序进行完全相同的交互。运行命令如下：
```bash
python3 kodrun.py [解答] < [测试]
```
其中 kodsoc.cpp 和 o1.h 必须位于同一文件夹中。交互器接受的输入格式在 kodsoc.cpp 文件的注释中有所描述。可通过运行命令 python3 kodrun.py -h 了解 kodrun.py 脚本的其他选项。
### 公平竞赛规则
禁止通过交互流程以外的方式在两个程序之间进行通信，例如通过一个程序延迟发送动作并由另一个程序读取时钟。如果评委发现程序之间存在非法通信的尝试，该提交可能被取消，情节严重者可能被取消参赛者在整个比赛中的资格。