以 P10832 为例配置 IO 通信题

chen_zhe · 2026-09-09 15:45:44 · 科技·工程

前文：https://www.luogu.com.cn/article/84bz48ew

对于需要运行两次的 IO 通信题，评测程序要把第一次运行的输出交给第二次运行，并检查它们是否共同完成了任务。本文以 P10832「[COTS 2023] 传 Mapa」 为例，介绍从输入输出约定、数据文件到评测代码和平台配置的完整做法。

下面直接使用 luogu-communication-lib 提供的接口。读者只需了解每个接口读写什么、何时调用，就能编写本题的评测逻辑，无需了解模板内部实现。文末还提供了一份用于检查评测流程的选手程序；它能够正确恢复数据，但不是 P10832 在最大数据上的满分做法。

题意简述

给定 n 对正整数 (x_i,y_i)，满足 1\le n\le100、1\le x_i,y_i\le10^9，且所有 x_i 两两不同。可以把 x_i 看作键，y_i 看作它对应的值。

选手提交的同一个程序需要独立运行两次。第一次读入全部键值对，将它们编码为长度为 k 的二进制串 s；第二次读入 s 和 q 个查询键，输出各个键对应的值。两次运行之间允许传递的信息由题目输入输出格式规定，选手不能依赖上一次运行留下的全局变量或其他外部状态。

编码串必须满足 1\le k\le6000。只有格式合法、解码正确且程序正常完成，才按编码长度计算得分。记一个测试点的得分比例为 r(k)，则

因此，k=3000 时得满分，k=4500 时得一半分数，k=6000 时即使全部回答正确，得分仍为零。编码非法或解码错误同样得零分，但评测时应区分这些原因。

评测思路

先考虑第二次运行的输入从哪里来。原始键值对可以提前写进测试文件，编码串却由选手程序决定，不同程序可能输出不同的合法编码。因此，评测时必须先运行编码程序，取得它的实际输出，再用这个输出组织解码输入。

我们把组织这两个阶段的代码写进 grader()。这个函数保存原始键值对，先取得并检查编码串，再把编码串和查询键交给第二次运行的选手程序。原始数据中的值可以直接用来核对解码答案，所以一份测试文件就足以完成整个过程。

要让平台运行这套检查，还需要外层交互器 checker.cpp。它读取测试文件，把原始数据发送给 grader，最后接收检查结果并计分。这样分工后，grader 负责两次运行之间的数据传递和答案检查，checker 负责测试文件与平台判定。注意，文件名中的 checker 不代表普通离线 SPJ；这份代码使用 registerInteraction()，应按交互器运行。

编写代码时，要区分选手与 grader 的通信，以及 grader 与 checker 的通信。前者严格使用题面给出的输入输出格式，后者使用我们约定的消息标记。消息标记只供评测程序使用，选手仍然编写普通的标准输入输出程序。

于是，一次测试点的执行过程为：checker 读取数据并发送给 grader，grader 先后运行编码和解码程序，确认结果正确后报告 k，最后由 checker 计分。平台只需启动一次这样的交互评测，两阶段运行由 grader 组织。

测试文件 .in
    │ 原始键值对
    ▼
checker.cpp  ←── 检查结果、编码长度 ── grader()
    └──────────── 原始数据 ────────────→ │
                                       ├─ 第一次运行：编码
                                       └─ 第二次运行：解码

输入输出与测试数据

grader 要向选手发送数据，首先必须确定选手会怎样读取这些数据。本题用第一行的 T 区分编码和解码；每次运行读入一个 T，完成对应阶段后退出。

编码阶段输入如下，其中第一行的 1 表示 T=1：

1
n
x1 y1
x2 y2
...
xn yn

选手输出长度 k 和二进制串 s：

k
s

解码阶段输入如下，其中 q 表示查询次数，s 必须是同一测试点编码阶段实际输出的串：

2
n q k
s
query1
query2
...
queryq

选手按查询顺序输出 q 个值：

answer1
answer2
...
answerq

原题允许 1\le q\le100。本例取 q=n，把全部键打乱顺序后各查询一次，保证每个键对应的值都被检查。乱序还可以配合适当的数据，检出只会按原输入顺序输出所有值的错误程序。选手仍应按输入给定的 q 处理查询，不应把本例的取值写死在程序中。

题面还应说明：每个阶段按数量读完输入、输出结果后正常退出，不要继续等待 EOF，也不要向标准输出添加调试信息。本例先发送本阶段的全部输入，选手正常退出时会刷新输出缓冲区。如果其他题在同一阶段内需要多轮问答，则应要求选手每轮输出后主动刷新。调试时也不要依赖这个模板环境中的 stderr 可用。

测试文件只需保存原始键值对。本例沿用所提供的 mapa-01-27.in 格式，第一行固定为 1，随后是 n 和 n 对整数。例如：

1
3
2 10
3 3
5 7

第一行的 1 由 checker 读掉，编码和解码阶段各自的 T 由 grader 生成。因此，一个 .in 就对应一次完整的两阶段测试，不要把两阶段拆成互不关联的两个测试点。如果重新设计数据格式，也可以去掉首行的 1，但必须同步修改 checker 的读取代码。

本例不读取标准答案文件。所提供的 mapa-01-27.in 与 .out 内容完全相同；这份 .out 没有参与答案判定。如果平台要求每个输入文件都有对应的输出文件，可以提供平台接受的占位文件。是否允许空文件需要看平台要求，不能仅凭 checker 没有使用它就省略上传。

编写评测代码

通信接口与消息格式

在编写本题逻辑前，准备好模板头文件 luogu-communication-lib.hpp 和与平台兼容的 testlib.h。前者供 grader 使用，后者供外层 checker 使用。模板应选择已验证的版本并记录提交号，方便今后复现评测环境。

通信模板需要使用的接口只有以下几个：

使用时可以始终站在 grader 的角度理解：p->fout 是“我写给选手的数据”，p->fin 是“我从选手读回的结果”。grader 自己的 cin 和 cout 留给外层 checker。两组流各有用途；每发送完一批对方接下来需要读取的数据，就调用 flush，避免数据仍留在缓冲区中。

checker 需要区分“检查失败”和“检查成功”，grader 也需要识别外层发来的数据。为此，本文约定三个字符串常量：INPUT_TOKEN 标记原始数据，WA_TOKEN 标记失败报告，OUTPUT_TOKEN 标记成功报告。两份源码中的常量值必须完全一致；正式配题时可以一起替换为该题专用的字符串。这些标记用于识别消息，运行隔离仍需模板和平台配合。

checker 发送的数据为：

INPUT_TOKEN
n
x1 y1
...
xn yn

grader 检查失败时发送：

WA_TOKEN
单行错误信息

检查成功时发送：

OUTPUT_TOKEN
k

以上 INPUT_TOKEN 等位置应写出常量对应的字符串内容。选手程序的输入输出中不出现这些标记。

interactive_lib.cpp

grader 先接收原始数据，再通过 safe_invoke() 启动编码程序，将 T=1、n 和全部键值对发送给它。收到编码结果后，必须检查 k 的范围、字符串的实际长度和每个字符是否合法，全部通过才能进入解码阶段。

检查编码串不必读入任意长的输出。先确认 k 合法，再用 setw(k + 1) 最多读取 k+1 个字符：读到不足 k 个或多于 k 个，都说明长度不符。这里读取的对象是 std::string，setw 指定的是最多提取的字符数，不需要为结束符额外留位。

编码程序正常退出后，grader 新运行一次选手程序，发送 T=2、n、q=n、k、编码串和乱序查询。代码用数组 order 保存原键值对的下标，第 i 个查询发送 x[order[i]]，对应的正确答案就是 y[order[i]]。由于 order 是全部下标的一个排列，每个键恰好检查一次；所有比较通过，就说明本次解码执行正确回答了全部查询。

随机种子 0x21792743 沿用案例文件，只用于生成查询顺序，不影响正确答案。固定种子便于在相同实现环境下复现；若更换标准库实现，不应假定 shuffle 的结果一定相同。

将以下代码保存为 interactive_lib.cpp，并在同目录准备模板头文件：

#include <bits/stdc++.h>
#include "luogu-communication-lib.hpp"

// 在洛谷实际使用时，应当把 luogu-communication-lib.hpp 的所有内容复制粘贴进 interactive_lib.cpp 中。

namespace {

const std::string INPUT_TOKEN = "mapa-tutorial-input-v1";
const std::string WA_TOKEN = "mapa-tutorial-wa-v1";
const std::string OUTPUT_TOKEN = "mapa-tutorial-output-v1";

[[noreturn]] void wrong_answer(const std::string &message) {
    std::cout << WA_TOKEN << '\n' << message << std::endl;
    std::exit(0);
}

void grader() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string token;
    if (!(std::cin >> token) || token != INPUT_TOKEN)
        wrong_answer("Invalid input token");

    int n;
    if (!(std::cin >> n) || n < 1 || n > 100)
        wrong_answer("Invalid n from checker");

    std::vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        if (!(std::cin >> x[i] >> y[i]))
            wrong_answer("Unable to read data from checker");
    }

    // 编码阶段。
    auto encoder = CommunicationLib::SubProcess::safe_invoke();
    encoder->fout << 1 << '\n' << n << '\n';
    for (int i = 0; i < n; ++i)
        encoder->fout << x[i] << ' ' << y[i] << '\n';
    encoder->fout << std::flush;

    int k;
    if (!(encoder->fin >> k))
        wrong_answer("Unable to read encoding length");
    if (k < 1 || k > 6000)
        wrong_answer("Encoding length is out of range");

    std::string s;
    // 最多读 k+1 个字符：多于 k 的串会被发现，且不需完整读入。
    if (!(encoder->fin >> std::setw(k + 1) >> s))
        wrong_answer("Unable to read encoding");
    if (s.size() != static_cast<std::size_t>(k))
        wrong_answer("Encoding length does not match");
    for (char c : s) {
        if (c != '0' && c != '1')
            wrong_answer("Encoding contains an invalid character");
    }
    encoder->guard();

    // 查询全部键，并打乱顺序。
    std::vector<int> order(n);
    std::iota(order.begin(), order.end(), 0);
    std::mt19937 rng(0x21792743);
    std::shuffle(order.begin(), order.end(), rng);

    // 解码阶段。
    auto decoder = CommunicationLib::SubProcess::safe_invoke();
    decoder->fout << 2 << '\n';
    decoder->fout << n << ' ' << n << ' ' << k << '\n';
    decoder->fout << s << '\n';
    for (int id : order)
        decoder->fout << x[id] << '\n';
    decoder->fout << std::flush;

    for (int i = 0; i < n; ++i) {
        int answer;
        if (!(decoder->fin >> answer)) {
            wrong_answer("Unable to read answer #" +
                         std::to_string(i + 1));
        }
        if (answer != y[order[i]]) {
            wrong_answer("Incorrect answer #" +
                         std::to_string(i + 1));
        }
    }
    decoder->guard();

    // 只有所有阶段通过后才能报告成功。
    std::cout << OUTPUT_TOKEN << '\n' << k << std::endl;
}

} // namespace

COMMUNICATION_LIB_REGISTER_GRADER(grader);

wrong_answer() 通过内部协议报告错误；其中的 exit(0) 不表示选手答案正确，外层 checker 会根据 WA_TOKEN 判错。崩溃、超时和非零退出等执行异常，还要由平台运行器处理，最终可能显示为 RE、TLE 或交互失败，不保证全部显示为 WA。

本实现按空白分隔读取字段，不严格检查每个换行位置，也不逐一拒绝合法结果之后的额外输出。如果另一个题必须严格拒绝尾随内容，需要连同输入输出结束方式一起设计。不要直接加入可能一直等待的“读到 EOF”循环，也不要假定 guard() 会主动给选手发送 EOF。

checker.cpp

checker 使用 registerInteraction() 初始化 testlib。inf 读取测试文件，ouf 读取对端返回的信息，cout 向对端发送数据。这里的 ouf 不是测试点的 .out 文件，代码也没有读取标准答案流。

checker 先检查数据范围和键是否重复，确认数据合法后才发送给 grader。接下来只需等待报告：若收到 WA_TOKEN，读取下一行错误信息并判错；若收到 OUTPUT_TOKEN，读取 k 并计分。grader 只有在全部答案正确、两阶段正常结束后才报告成功，checker 因而可以直接使用这个检查结果。

#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

const string INPUT_TOKEN = "mapa-tutorial-input-v1";
const string WA_TOKEN = "mapa-tutorial-wa-v1";
const string OUTPUT_TOKEN = "mapa-tutorial-output-v1";

int main(int argc, char *argv[]) {
    registerInteraction(argc, argv);

    // 保留案例测试文件第一行固定为 1 的格式。
    int type = inf.readInt(1, 1, "type");
    (void)type;
    int n = inf.readInt(1, 100, "n");

    vector<int> x(n), y(n);
    set<int> keys;
    for (int i = 0; i < n; ++i) {
        x[i] = inf.readInt(1, 1000000000, "x");
        y[i] = inf.readInt(1, 1000000000, "y");
        if (!keys.insert(x[i]).second)
            quitf(_fail, "Duplicate key in test data");
    }

    cout << INPUT_TOKEN << '\n' << n << '\n';
    for (int i = 0; i < n; ++i)
        cout << x[i] << ' ' << y[i] << '\n';
    cout << flush;

    string token = ouf.readToken();
    if (token == WA_TOKEN) {
        ouf.readEoln();
        string message = ouf.readLine();
        quitf(_wa, "%s", message.c_str());
    }
    if (token != OUTPUT_TOKEN)
        quitf(_wa, "Invalid output token");

    int k = ouf.readInt();
    if (k < 1 || k > 6000)
        quitf(_wa, "Invalid encoding length: %d", k);

    if (k <= 3000)
        quitf(_ok, "Accepted (k=%d)", k);

    double score = 1.0 - double(k - 3000) / 3000.0;
    quitp(score, "Acceptable (k=%d)", k);
}

错误信息使用 quitf(_wa, "%s", message.c_str()) 输出，避免把消息中的字符当成格式说明。无效长度也显式判错，不依赖“这个分支不会发生”的假设。

quitp() 接收的是 [0,1] 内的比例。例如 k=4500 时传入 0.5，若该测试点满分为 10 分，应得到 5 分。测试点分值、舍入方式以及子任务是求和还是取最小值，都需要在平台上另行配置。如果题目只判 AC/WA，检查成功后直接使用 quitf(_ok, "Accepted") 即可。

联调程序与复杂度

配置完成后，先用一份容易核对的选手程序检查数据是否正确传递。

:::info[不重要的复杂度分析]{open}

因为 x_i,y_i\le10^9<2^{30}，可以把每个键和值各写成固定的 30 位二进制数，每对占 60 位，总编码长度为 k=60n。

解码时每次取出连续的 30 位，按原顺序恢复键和值，再存入 map。固定长度保证每个整数的边界唯一，二进制展开与恢复互为逆操作；由于键两两不同，重建后的映射与原数据相同，因此每次查询都会得到正确的值。

这份程序能够检查编码、转交字符串和解码是否衔接正确。它没有进一步压缩数据，n=100 时编码长 6000 位，按题目规则只能得到零分比例。

编码阶段时间复杂度为 O(30n)，保存编码串需要 O(30n) 空间。解码阶段先读取 60n 位，再建立映射并回答查询，时间复杂度为 O(30n+(n+q)\log(n+1))，空间复杂度为 O(30n+n)。将位数 30 视为常数后，编码为 O(n) 时间，解码为 O((n+q)\log(n+1)) 时间，两阶段空间均为 O(n)。

另外，评测代码自身也有开销。checker 用 set 检查重复键，时间为 O(n\log(n+1))、空间为 O(n)；grader 保存映射、打乱查询并检查长度为 k 的编码，处理合法输出的时间与空间均为 O(n+k)。这些复杂度不包含选手算法耗时、程序启动和等待退出的时间，实际时限仍应通过平台运行验证。题目整数和该基准程序的 30 位恢复过程均不会超过 int 范围。

:::

将以下程序保存为 baseline.cpp：

#include <bits/stdc++.h>
using namespace std;

// 每个整数固定写入 30 位，保留前导零以确定解码边界。
void append30(string &s, int value) {
    for (int bit = 29; bit >= 0; --bit)
        s.push_back(char('0' + ((value >> bit) & 1)));
}

// 从 pos 开始恢复一个整数，并将 pos 移到下一个整数的起点。
int read30(const string &s, int &pos) {
    int value = 0;
    for (int bit = 0; bit < 30; ++bit)
        value = value * 2 + (s[pos++] - '0');
    return value;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int type;
    if (!(cin >> type)) return 1;

    if (type == 1) {
        int n;
        cin >> n;
        string s;
        for (int i = 0; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            append30(s, x);
            append30(s, y);
        }
        cout << s.size() << '\n' << s << '\n';
    } else if (type == 2) {
        int n, q, k;
        string s;
        cin >> n >> q >> k >> s;
        if (k != 60 * n || static_cast<int>(s.size()) != k)
            return 1;

        map<int, int> values;
        int pos = 0;
        for (int i = 0; i < n; ++i) {
            int x = read30(s, pos);
            int y = read30(s, pos);
            values[x] = y;
        }
        for (int i = 0; i < q; ++i) {
            int x;
            cin >> x;
            auto it = values.find(x);
            if (it == values.end()) return 1;
            cout << it->second << '\n';
        }
    } else {
        return 1;
    }
    return 0;
}

同一份程序可以用于检查三个评分分支：

所提供的 mapa-01-27.in 满足 n=100，因此用这份程序测试时，零分比例本身是正常的。应同时查看交互器消息，确认原因是编码长度，而非未正确完成评测。这里的三个规模用于验收计分，并不表示正式数据应当采用这样的规模分布。

验收与常见问题

先把 baseline.cpp 单独编译，运行编码阶段，再将得到的字符串组织成解码输入，核对查询答案。这一步确认选手程序自身没有写错。随后把同一份源码交给目标平台，通过通信库构建和交互运行器再测一次，才能确认评测配置也正确。两次测试检查的对象不同，都需要完成。

正确程序通过后，还要故意构造错误输出和异常执行，确认它们不会得到正常成功分数。建议分别检查以下情况：

正式数据还应覆盖 n=1、最大规模、数值 1 与 10^9、不同输入顺序、不同键分布和重复的值。键必须始终两两不同。基准程序只验证通信流程，正式数据的强度仍要结合预期算法和合理错误算法检查。

如果出现 Invalid input token，先看两个文件的消息常量是否一致，以及是否通过完整交互运行器启动。如果选手直接读到了 token，则应检查通信库有没有正确加入构建。多个 main() 的链接错误通常意味着误把 checker 与选手代码合并；找不到头文件则应检查依赖是否上传或展开。

程序输出结果后仍然卡住时，优先检查是否继续等 EOF、是否忘记刷新、是否没有退出，以及是否在读取输入前大量输出。编码完成但读不到解码答案时，检查选手是否正确处理了 T=2，是否依次读入了 n,q,k、编码串和查询。所有回答正确却得零分时，先确认 k，再检查平台是否正确解析部分分；k=4500 应得一半分数，是很方便的定位用例。

迁移到其他 IO 通信题时，先重新定义每阶段的输入输出和允许传递的信息，再修改原始数据格式、grader 的各阶段操作及答案检查，最后修改 checker 的计分方式。通信模板仍按接口调用，平台的构建、交互运行和验收步骤也可以沿用。