跳转至

Checker

Checker，即 Special Judge，用於檢驗答案是否合法。使用 Testlib 可以讓我們免去檢驗許多東西，使編寫簡單許多。

Checker 從命令行參數讀取到輸入文件名、選手輸出文件名、標準輸出文件名，並確定選手輸出是否正確，並返回一個預定義的結果：

請在閲讀下文前先閲讀 通用。

簡單的例子

Note

給定兩個整數 \(a,b\)（\(-1000 \le a,b \le 1000\)），輸出它們的和。

這題顯然不需要 checker 對吧，但是如果一定要的話也可以寫一個：

 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，求 \(s\) 到 \(t\) 的最長路並輸出路徑（可能有多條，輸出任一）。

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

不好的實現

 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 或修改格式時變得困難。

讀入標準輸出和選手輸出的方式實際上是完全相同的，這就是我們通常編寫一個用流作為參數的讀入函數的原因。

好的實現

 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 行也可以等價地寫成如下形式：

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

請在 readAns 中避免調用 全局 函數 ::ensure/ensuref()，這會導致在某些應判為 WA 的選手輸出下返回 _fail，產生錯誤。

建議與常見錯誤

  • 編寫 readAns 函數，它真的可以讓你的 checker 變得很棒。

  • 讀入選手輸出時永遠限定好範圍，如果某些變量忘記了限定且被用於某些參數，你的 checker 可能會判定錯誤或 RE 等。

    • 反面教材
     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
    • 正面教材
    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 會幫我們做好這一切。但是如果需要的話，以以下格式在命令行運行：

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

一些預設的 checker

很多時候我們的 checker 完成的工作很簡單（如判斷輸出的整數是否正確，輸出的浮點數是否滿足精度要求），Testlib 已經為我們給出了這些 checker 的實現，我們可以直接使用。

一些常用的 checker 有：

  • ncmp：按順序比較 64 位整數。
  • rcmp4：按順序比較浮點數，最大可接受誤差（絕對誤差或相對誤差）不超過 \(10^{-4}\)（還有 rcmp6，rcmp9 等對精度要求不同的 checker，用法和 rcmp4 類似）。
  • wcmp：按順序比較字符串（不帶空格，換行符等非空字符）。

  • yesno：比較 YES 和 NO，大小寫不敏感。

    本文主要翻譯自 Checkers with testlib.h - Codeforces。testlib.h 的 GitHub 存儲庫為 MikeMirzayanov/testlib。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用