Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
237 lines (194 sloc) 8.07 KB

Checker,即 Special Judge ,用于检验答案是否合法。使用 Testlib 可以让我们免去检验许多东西,使编写简单许多。

Checker 从命令行参数读取到输入文件名、选手输出文件名、标准输出文件名,并确定选手输出是否正确,并返回一个预定义的结果:

请在阅读下文前先阅读 通用

简单的例子

???+note 题目 给定两个整数 $a,b$ ( $-1000 \le a,b \le 1000$ ),输出它们的和。

这题显然不需要 checker 对吧,但是如果一定要的话也可以写一个:

#include "testlib.h"

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

  int pans = ouf.readInt(-2000, 2000, "sum of numbers");

  // 假定标准输出是正确的,不检查其范围
  // 之后我们会看到这并不合理
  int jans = ans.readInt();

  if (pans == jans)
    quitf(_ok, "The sum is correct.");
  else
    quitf(_wa, "The sum is wrong: expected = %d, found = %d", jans, pans);
}

编写 readAns 函数

假设你有一道题输入输出均有很多数,如:给定一张 DAG,求 $s$ 到 $t$ 的最长路并输出路径(可能有多条,输出任一)。

下面是一个 不好 的 checker 的例子。

不好的实现

#include <map>
#include <vector>
#include "testlib.h"
using namespace std;

map<pair<int, int>, int> edges;

int main(int argc, char* argv[]) {
  registerTestlibCmd(argc, argv);
  int n = inf.readInt();  // 不需要 readSpace() 或 readEoln()
  int m = inf.readInt();  // 因为不需要在 checker 中检查标准输入合法性(有
                          // validator)
  for (int i = 0; i < m; i++) {
    int a = inf.readInt();
    int b = inf.readInt();
    int w = inf.readInt();
    edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
  }
  int s = inf.readInt();
  int t = inf.readInt();

  // 读入标准输出
  int jvalue = 0;
  vector<int> jpath;
  int jlen = ans.readInt();
  for (int i = 0; i < jlen; i++) {
    jpath.push_back(ans.readInt());
  }
  for (int i = 0; i < jlen - 1; i++) {
    jvalue += edges[make_pair(jpath[i], jpath[i + 1])];
  }

  // 读入选手输出
  int pvalue = 0;
  vector<int> ppath;
  vector<bool> used(n, false);
  int plen = ouf.readInt(2, n, "number of vertices");  // 至少包含 s 和 t 两个点
  for (int i = 0; i < plen; i++) {
    int v = ouf.readInt(1, n, format("path[%d]", i + 1).c_str());
    if (used[v - 1])  // 检查每条边是否只用到一次
      quitf(_wa, "vertex %d was used twice", v);
    used[v - 1] = true;
    ppath.push_back(v);
  }
  // 检查起点终点合法性
  if (ppath.front() != s)
    quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s,
          ppath.front());
  if (ppath.back() != t)
    quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t,
          ppath.back());
  // 检查相邻点间是否有边
  for (int i = 0; i < plen - 1; i++) {
    if (edges.find(make_pair(ppath[i], ppath[i + 1])) == edges.end())
      quitf(_wa, "there is no edge (%d, %d) in the graph", ppath[i],
            ppath[i + 1]);
    pvalue += edges[make_pair(ppath[i], ppath[i + 1])];
  }

  if (jvalue != pvalue)
    quitf(_wa, "jury has answer %d, participant has answer %d", jvalue, pvalue);
  else
    quitf(_ok, "answer = %d", pvalue);
}

这个 checker 主要有两个问题:

  1. 它确信标准输出是正确的。如果选手输出比标准输出更优,它会被判成 WA,这不太妙。同时,如果标准输出不合法,也会产生 WA。对于这两种情况,正确的操作都是返回 Fail 状态。
  2. 读入标准输出和选手输出的代码是重复的。在这道题中写两遍读入问题不大,只需要一个 for 循环;但是如果有一道题输出很复杂,就会导致你的 checker 结构混乱。重复代码会大大降低可维护性,让你在 debug 或修改格式时变得困难。

读入标准输出和选手输出的方式实际上是完全相同的,这就是我们通常编写一个用流作为参数的读入函数的原因。

好的实现

#include <map>
#include <vector>
#include "testlib.h"
using namespace std;

map<pair<int, int>, int> edges;
int n, m, s, t;

// 这个函数接受一个流,从其中读入
// 检查路径的合法性并返回路径长度
// 当 stream 为 ans 时,所有 stream.quitf(_wa, ...)
// 和失败的 readXxx() 均会返回 _fail 而非 _wa
// 也就是说,如果输出非法,对于选手输出流它将返回 _wa,
// 对于标准输出流它将返回 _fail
int readAns(InStream& stream) {
  // 读入输出
  int value = 0;
  vector<int> path;
  vector<bool> used(n, false);
  int len = stream.readInt(2, n, "number of vertices");
  for (int i = 0; i < len; i++) {
    int v = stream.readInt(1, n, format("path[%d]", i + 1).c_str());
    if (used[v - 1]) {
      stream.quitf(_wa, "vertex %d was used twice", v);
    }
    used[v - 1] = true;
    path.push_back(v);
  }
  if (path.front() != s)
    stream.quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s,
                 path.front());
  if (path.back() != t)
    stream.quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t,
                 path.back());
  for (int i = 0; i < len - 1; i++) {
    if (edges.find(make_pair(path[i], path[i + 1])) == edges.end())
      stream.quitf(_wa, "there is no edge (%d, %d) in the graph", path[i],
                   path[i + 1]);
    value += edges[make_pair(path[i], path[i + 1])];
  }
  return value;
}

int main(int argc, char* argv[]) {
  registerTestlibCmd(argc, argv);
  n = inf.readInt();
  m = inf.readInt();
  for (int i = 0; i < m; i++) {
    int a = inf.readInt();
    int b = inf.readInt();
    int w = inf.readInt();
    edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
  }
  int s = inf.readInt();
  int t = inf.readInt();

  int jans = readAns(ans);
  int pans = readAns(ouf);
  if (jans > pans)
    quitf(_wa, "jury has the better answer: jans = %d, pans = %d\n", jans,
          pans);
  else if (jans == pans)
    quitf(_ok, "answer = %d\n", pans);
  else  // (jans < pans)
    quitf(_fail, ":( participant has the better answer: jans = %d, pans = %d\n",
          jans, pans);
}

注意到这种写法我们同时也检查了标准输出是否合法,这样写 checker 让程序更短,且易于理解和 debug。此种写法也适用于输出 YES(并输出方案什么的),或 NO 的题目。

???+ note 对于某些限制的检查可以用 InStream::ensure/ensuref() 函数更简洁地实现。如上例第 21 至 23 行也可以等价地写成如下形式:

```cpp
stream.ensuref(!used[v - 1], "vertex %d was used twice", v);
```

???+ warning 请在 readAns 中避免调用 全局 函数 ::ensure/ensuref() ,这会导致在某些应判为 Wrong Answer 的选手输出下返回 _fail ,产生错误。

建议与常见错误

  • 编写 readAns 函数,它真的可以让你的 checker 变得很棒。

  • 读入选手输出时永远限定好范围,如果某些变量忘记了限定且被用于某些参数,你的 checker 可能会判定错误或 RE 等。

    反面教材
    // ....
    int k = ouf.readInt();
    vector<int> lst;
    for (int i = 0; i < k; i++)  // k = 0 和 k = -5 在这里作用相同(不会进入循环体)
      lst.push_back(
          ouf.readInt());  // 但是我们并不想接受一个长度为 -5 的 list,不是吗?
    // ....
    int pos = ouf.readInt();
    int x =
        A[pos];  // 100% 会 RE。一定会有人输出 -42, 2147483456 或其他一些非法数字。
                 // ....
    正面教材
    // ....
    int k = ouf.readInt(0, n);  // 负数会 PE
    vector<int> lst;
    for (int i = 0; i < k; i++) lst.push_back(ouf.readInt());
    // ....
    int pos = ouf.readInt(0, (int)A.size() - 1);  // 防止 out of range
    int x = A[pos];
    // ....
  • 使用项别名

    本文翻译自 Checkers with testlib.h - Codeforcestestlib.h 的 GitHub 存储库为 MikeMirzayanov/testlib

You can’t perform that action at this time.