跳转至

Checker

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

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

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

简单的例子

Note

给定两个整数 a,b1000a,b1000),输出它们的和。

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

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
#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,求 st 的最长路并输出路径(可能有多条,输出任一)。

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

不好的实现

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// clang-format off

#include "testlib.h"
#include <map>
#include <vector>
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 或修改格式时变得困难。

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

好的实现

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// clang-format off

#include "testlib.h"
#include <map>
#include <vector>
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() 函数更简洁地实现。如上例第 23 至 25 行也可以等价地写成如下形式:

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

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

建议与常见错误

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

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

    • 反面教材
    C++
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    // ....
    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];
    // 可能会有人输出 -42, 2147483456 或其他一些非法数字导致 checker RE
    
    • 正面教材
    C++
    1
    2
    3
    4
    5
    6
    7
    8
    // ....
    int k = ouf.readInt(0, n);  // 长度不合法会立刻判 WA 而不会继续 check 导致 RE
    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];
    // ....
    
  • 使用项别名。

  • 和 validator 不同,checker 不用特意检查非空字符。例如对于一个按顺序比较整数的 checker,我们只需判断选手输出的整数和答案整数是否对应相等,而选手是每行输出一个整数,还是在一行中输出所有整数等格式问题,我们的 checker 不必关心。

使用方法

通常我们不需要本地运行它,评测工具/OJ 会帮我们做好这一切。但是如果需要的话,以以下格式在命令行运行:

Bash
1
./checker <input-file> <output-file> <answer-file> [<report-file> [<-appes>]]

一些预设的 checker

很多时候我们的 checker 完成的工作很简单(如判断输出的整数是否正确,输出的浮点数是否满足精度要求),Testlib 已经为我们给出了这些 checker 的实现,我们可以直接使用。

一些常用的 checker 有:

  • ncmp:按顺序比较 64 位整数。
  • rcmp4:按顺序比较浮点数,最大可接受误差(绝对误差或相对误差)不超过 104(还有 rcmp6,rcmp9 等对精度要求不同的 checker,用法和 rcmp4 类似)。
  • wcmp:按顺序比较字符串(不带空格,换行符等非空字符)。
  • yesno:比较 YES 和 NO,大小写不敏感。

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


0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn
0594codes.cn