概述

示例题目下载通道：http://8.136.99.126/file/3/P98.zip

事实证明，Hydro 还是支持通信题评测的——

众所周知，通信题需要提交两个程序 A 和 B。A 需要向 B 传递有限的信息，以帮助 B 计算出正确的结果。

下面以这样一道题目为例：

给定两个长度为 $n$ 且至多有一个字符不同的 01 串 $S,T$。

请构造两个程序 A 和 B，实现以下操作：

1. A 读入 01 串 $S$。
2. A 输出一个不大于 $\color{red}2^{31}-1$ 的非负整数 $X$。
3. B 读入 01 串 $T$ 和 A 输出的非负整数 $X$。
4. B 输出 $S,T$ 之间不同的那个位置。

特别地，给定的两个 01 串有可能完全相同，此时请输出 $0$。

对于 $100\%$ 的数据，$1 \le n \le 10^6$。

（本题存在加强版，加强版中要求 A 输出的非负整数不大于 $\color{red}2^{20}-1$）

很明显，我们不能使用传统题提交，因为提交的是两个程序。一种可行的方案是，要求选手用指定的分隔符（示例题目中为 /* ATTENTION!!! THIS IS THE BARRIER!!! */）将两个程序分开，然后以提交答案的方式提交。

为了以提交答案的方式提交，我们的 config.yaml 应该这样配置：

type: submit_answer # 提交答案题
subType: single
filename: code.txt
checker_type: testlib
checker: checker.cpp # 评测程序
subtasks: # 测试数据（与传统题相同）
  - score: 100
    if: []
    id: 1
    type: sum
    cases:
      - input: 1.in
        output: 1.out
      - input: 2.in
        output: 2.out
      - input: 3.in
        output: 3.out
      - input: 4.in
        output: 4.out
      - input: 5.in
        output: 5.out
      - input: 6.in
        output: 6.out
      - input: 7.in
        output: 7.out
      - input: 8.in
        output: 8.out
      - input: 9.in
        output: 9.out
      - input: 10.in
        output: 10.out
      - input: 11.in
        output: 11.out
      - input: 12.in
        output: 12.out
      - input: 13.in
        output: 13.out
      - input: 14.in
        output: 14.out
      - input: 15.in
        output: 15.out
      - input: 16.in
        output: 16.out
      - input: 17.in
        output: 17.out
      - input: 18.in
        output: 18.out
      - input: 19.in
        output: 19.out
      - input: 20.in
        output: 20.out

在接下来的操作中，我们会将字符串 $S$ 放在输入文件中，$S,T$ 之间不同的位置编号放在输出文件中，而字符串 $T$ 将由评测程序自行生成。

评测程序编写

评测问题

分开两个程序并分别存储

const string BARRIER = "/* ATTENTION!!! THIS IS THE BARRIER!!! */\n"; // 分界线
const int LINE_LIMIT = 1000, SIZE_LIMIT = 100000, TIME_LIMIT = 1000;
// 代码行数限制，代码长度限制（字节）和时间限制（毫秒）
int main(int argc, char** argv)
{
  // ...
  ofstream p1("one.cc"); // 程序 A
  string source = ""; // 程序 B
  int l = LINE_LIMIT, z = SIZE_LIMIT; // 监测代码行数和长度，并拒绝评测过长的代码
  bool split = false; // 程序 A 是否结束
  while (!ouf.eof())
  {
    string s = ouf.readLine();
    s += '\n';
    l--, z -= s.size();
    if (l <= 0 || z <= 0) wrong("You cheated!");
    if (s == BARRIER) split = true;
    if (!split) p1 << s; // 将程序 A 输出到文件
    else source += s;
  }
  p1.close();
  // ...
  system("mkdir twos");
  ofstream p4("two.cc");
  p4 << source; // 将程序 B 输出到文件
  p4.close();
  // ...
}

获取数据和程序输入输出

int convert(string s) // 将字符串转换为整数
{
  if (s.size() < 1 || s.size() > 10) return -1;
  long long x = 0;
  for (unsigned int i = 0; i < s.size(); i++)
  {
    if (s[i] < '0' || s[i] > '9') return -1;
    x = x * 10 + s[i] - '0';
  }
  if (x > INT_MAX) return -1; // 给出的字符串不合法
  // 此处出现了加强版与原版唯一的一处不同点：加强版的评测程序会把 INT_MAX 换成 (1 << 20) - 1。
  return x;
}
int main(int argc, char** argv)
{
  // ...
  ofstream p2("ones/first.txt"); // 程序 A 输入
  p2 << input << endl;
  p2.close();
  // ...
  ifstream p3("ones/second.txt"); // 程序 A 输出
  string middle = "", t;
  while (getline(p3, t)) middle += t;
  int transfer = convert(middle); // 转换输出，-1 代表输出不合法
  if (transfer == -1) wrong("Program A didn't work!");
  ofstream p5("twos/third.txt"); // 程序 B 输入
  int answer = ans.readInt();
  if (answer) input[answer - 1] ^= 1; // 生成字符串 T
  p5 << input << endl;
  p5 << transfer << endl;
  p5.close();
  // ...
  int time2 = time_taken2.count();
  ifstream p6("twos/fourth.txt"); // 程序 B 输出
  string finals = "";
  while (getline(p6, t)) finals += t;
  int output = convert(finals);
  if (output == -1) wrong("Program B didn't work!");
  p6.close();
  if (output != answer) wrong("Wrong answer!"); // 答案错误
  correct(time1, time2); // 答案正确
  return 0;
}

编译运行程序并计时

int main(int argc, char** argv)
{
  // ...
  system("g++ -o one one.cc -O2 -std=c++14"); // 编译程序 A
  system("mv one ones/");
  std::chrono::high_resolution_clock::time_point start1 = std::chrono::high_resolution_clock::now();
  system("(ulimit -u 1 && ulimit -t 2 && ulimit -m 524288 && ulimit -s 524288 && ./ones/one < ones/first.txt > ones/second.txt)");
  // 运行程序 A（绑定 stdin / stdout 至 ones/first.txt / ones/second.txt，限制：2 秒，512 MB，1 个线程）
  std::chrono::high_resolution_clock::time_point end1 = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double, milli> time_taken1 = end1 - start1;
  int time1 = time_taken1.count(); // 程序 A 用时（毫秒）
  if (time1 > TIME_LIMIT) wrong("Program A didn't work!"); // 程序 A 超时
  // ...
  system("g++ -o two two.cc -O2 -std=c++14"); // 编译程序 B
  system("mv two twos/");
  std::chrono::high_resolution_clock::time_point start2 = std::chrono::high_resolution_clock::now();
  system("(ulimit -u 1 && ulimit -t 2 && ulimit -m 524288 && ulimit -s 524288 && ./twos/two < twos/third.txt > twos/fourth.txt)");
  // 运行程序 B（绑定 stdin / stdout 至 twos/third.txt / twos/fourth.txt，限制：2 秒，512 MB，1 个线程）
  std::chrono::high_resolution_clock::time_point end2 = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double, milli> time_taken2 = end2 - start2;
  int time2 = time_taken2.count(); // 程序 B 用时（毫秒）
  if(time2 > TIME_LIMIT) wrong("Program B didn't work!"); // 程序 B 超时
  // ...
  correct(time1, time2);  // 答案正确，报告程序用时
  return 0;
}
// 请注意：此处的实现中，时间限制对两个程序分别生效，而不是对二者用时之和生效。

安全问题

快速筛查违规函数（非必需）

void replace(string &s) // 过滤 "##"（在筛查前过滤）
{
  while (1)
  {
    int x = s.find("##");
    if (x == -1) break;
    s.replace(x, 2, "");
  }
}
bool check(string s) // 筛查违规函数
{
  if (s.find("open") != string::npos) return true; // POSIX "open", "fopen", "freopen" and such functions
  if (s.find("close") != string::npos) return true; // POSIX "close", "fclose" and such functions
  if (s.find("file") != string::npos) return true; // C++17 <filesystem> header
  if (s.find("FILE") != string::npos) return true; // C style FILE pointer
  if (s.find("fstream") != string::npos) return true; // <fstream> header, ifstream, ofstream
  if (s.find("dup") != string::npos) return true; // "dup" and "dup2" functions in <fcntl.h>
  if (s.find("system") != string::npos) return true; // C++17 <filesystem> header, "system" function
  if (s.find("exec") != string::npos) return true; // "exec-" function class
  return false; // 未筛查出违规函数
}
int main()
{
    // ...
    replace(s);
    if (check(s)) wrong("You cheated!");
    // ...
}
// 请注意，此部分只用于快速筛查（节省不必要的编译时间），可以删去！

隐藏 stderr 信息（防止套取数据等）

int original_stderr; // 用于恢复 stderr 定向
void wrong(string s) // 返回 WA
{
  dup2(original_stderr, STDERR_FILENO); // 恢复 stderr 定向，否则将无法正常返回评测结果
  quitf(_wa, s.c_str());
  exit(0);
}
void correct(int t1, int t2) // 返回 AC
{
  dup2(original_stderr, STDERR_FILENO);
  quitf(_ok, "Accepted! (%dms / %dms)", t1, t2); // 报告程序用时
  exit(0);
}
int main()
{
  registerTestlibCmd(argc, argv); // 该指令重定向了 stderr
  original_stderr = dup(STDERR_FILENO); // 保存当前 stderr 定向
  freopen("comments.txt", "w", stderr); // 重定向 stderr
  // ...
  system("rm -rf *"); // 在程序 A 运行结束后清空 comments.txt，防止被程序 A 利用
  freopen("comments.txt", "w", stderr); // 重新创建 comments.txt
  // ...
}

监测并制止程序 A 偷偷使用文件传输信息的行为（核心部分）

const string templates = // 应出现的文件（主目录和 ones/ 目录）
R"(
.
..
comments.txt
one.cc
ones

.
..
first.txt
one
second.txt
)";
void monitor(string &s, string t) // 利用管道获取 ls 指令的输出结果
{
  array<char, 1048576> buffer;
  FILE* pipe = popen(t.c_str(), "r");
  try
  {
    while (fgets(buffer.data(), buffer.size(), pipe) != nullptr) s += buffer.data();
  }
  catch (...)
  {
    pclose(pipe);
    throw;
  }
}
int main(int argc, char** argv) // 在程序 A 运行结束后扫描目录中的文件
{
  system("rm -rf *"); // 删除所有无关文件，防止被程序 A 利用
  // ...
  string result = "\n"; // 存储 ls 指令的输出结果
  monitor(result, "/bin/bash -c 'ls -at | sort -V'"); // 扫描主目录中的文件并按文件名字典序升序输出
  result += "\n"; // 隔开两个目录的扫描结果
  monitor(result, "/bin/bash -c 'ls -at ones | sort -V'"); // 扫描 ones/ 目录中的文件并按文件名字典序升序输出
  if (result != templates) wrong("You cheated!"); // 如果扫描结果与预期不同，那么程序 A 一定在偷偷使用文件传输信息
  system("rm -rf *");
  // ...
}

完整实现

#include <bits/stdc++.h>
#include <chrono>
#include "testlib.h"
using namespace std;
const string BARRIER = "/* ATTENTION!!! THIS IS THE BARRIER!!! */\n";
const string templates =
R"(
.
..
comments.txt
one.cc
ones

.
..
first.txt
one
second.txt
)";
const int LINE_LIMIT = 1000, SIZE_LIMIT = 100000, TIME_LIMIT = 1000;
int original_stderr;
void replace(string &s)
{
  while (1)
  {
    int x = s.find("##");
    if (x == -1) break;
    s.replace(x, 2, "");
  }
}
bool check(string s)
{
  if (s.find("open") != string::npos) return true;
  if (s.find("close") != string::npos) return true;
  if (s.find("file") != string::npos) return true;
  if (s.find("FILE") != string::npos) return true;
  if (s.find("fstream") != string::npos) return true;
  if (s.find("dup") != string::npos) return true;
  if (s.find("system") != string::npos) return true;
  if (s.find("exec") != string::npos) return true;
  return false;
}
int convert(string s)
{
  if (s.size() < 1 || s.size() > 10) return -1;
  long long x = 0;
  for (unsigned int i = 0; i < s.size(); i++)
  {
    if (s[i] < '0' || s[i] > '9') return -1;
    x = x * 10 + s[i] - '0';
  }
  if (x > INT_MAX) return -1;
  return x;
}
void wrong(string s)
  dup2(original_stderr, STDERR_FILENO);
  quitf(_wa, s.c_str());
  exit(0);
}
void correct(int t1, int t2)
{
  dup2(original_stderr, STDERR_FILENO);
  quitf(_ok, "Accepted! (%dms / %dms)", t1, t2);
  exit(0);
}
void monitor(string &s, string t)
{
  array<char, 1048576> buffer;
  FILE* pipe = popen(t.c_str(), "r");
  try
  {
    while (fgets(buffer.data(), buffer.size(), pipe) != nullptr) s += buffer.data();
  }
  catch (...)
  {
    pclose(pipe);
    throw;
  }
}
int main(int argc, char** argv)
{
  registerTestlibCmd(argc, argv);
  system("rm -rf *");
  original_stderr = dup(STDERR_FILENO);
  freopen("comments.txt", "w", stderr);
  system("mkdir ones");
  ofstream p1("one.cc"), p2("ones/first.txt");
  string source = "";
  int l = LINE_LIMIT, z = SIZE_LIMIT;
  bool split = false;
  while (!ouf.eof())
  {
    string s = ouf.readLine();
    s += '\n';
    l--, z -= s.size();
    replace(s);
    if (l <= 0 || z <= 0 || check(s)) wrong("You cheated!");
    if (s == BARRIER) split = true;
    if (!split) p1 << s;
    else source += s; 
  }
  string input = inf.readLine();
  p2 << input << endl;
  p1.close(), p2.close();
  system("g++ -o one one.cc -O2 -std=c++14");
  system("mv one ones/");
  std::chrono::high_resolution_clock::time_point start1 = std::chrono::high_resolution_clock::now();
  system("(ulimit -u 1 && ulimit -t 2 && ulimit -m 524288 && ulimit -s 524288 && ./ones/one < ones/first.txt > ones/second.txt)");
  std::chrono::high_resolution_clock::time_point end1 = std::chrono::high_resolution_clock::now();
  string result = "\n";
  monitor(result, "/bin/bash -c 'ls -at | sort -V'");
  result += "\n";
  monitor(result, "/bin/bash -c 'ls -at ones | sort -V'");
  if (result != templates) wrong("You cheated!");
  std::chrono::duration<double, milli> time_taken1 = end1 - start1;
  int time1 = time_taken1.count();
  ifstream p3("ones/second.txt");
  string middle = "", t;
  while (getline(p3, t)) middle += t;
  int transfer = convert(middle);
  if (transfer == -1 || time1 > TIME_LIMIT) wrong("Program A didn't work!");
  p3.close();
  fclose(stderr);
  system("rm -rf *");
  freopen("comments.txt", "w", stderr);
  system("mkdir twos");
  ofstream p4("two.cc");
  p4 << source;
  p4.close();
  system("g++ -o two two.cc -O2 -std=c++14");
  system("mv two twos/");
  ofstream p5("twos/third.txt");
  int answer = ans.readInt();
  if (answer) input[answer - 1] ^= 1;
  p5 << input << endl;
  p5 << transfer << endl;
  p5.close();
  std::chrono::high_resolution_clock::time_point start2 = std::chrono::high_resolution_clock::now();
  system("(ulimit -u 1 && ulimit -t 2 && ulimit -m 524288 && ulimit -s 524288 && ./twos/two < twos/third.txt > twos/fourth.txt)");
  std::chrono::high_resolution_clock::time_point end2 = std::chrono::high_resolution_clock::now();
  std::chrono::duration<double, milli> time_taken2 = end2 - start2;
  int time2 = time_taken2.count();
  ifstream p6("twos/fourth.txt");
  string finals = "";
  while (getline(p6, t)) finals += t;
  int output = convert(finals);
  if (output == -1 || time2 > TIME_LIMIT) wrong("Program B didn't work!");
  p6.close();
  if (output != answer) wrong("Wrong answer!");
  correct(time1, time2);
  return 0;
}

附录：示例题目题解

原版

Hash 模板题。本题随便用什么 Hash 函数都能过，比如「所有 $\texttt{1}$ 的位置编号之和 $\text{mod } 12345678$」。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string S;
    cin >> S;
    int X = 0;
    int n = S.size();
    S = ' ' + S;
    const int P = 12345678;
    for (int i = 1; i <= n; i++)
        if (S[i] == '1') X = (X + i) % P;
    cout << X << endl;
    return 0;
}

/* ATTENTION!!! THIS IS THE BARRIER!!! */

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string T;
    int X;
    cin >> T >> X;
    int D = 0;
    int n = T.size();
    T = ' ' + T;
    const int P = 12345678;
    int Y = 0;
    for (int i = 1; i <= n; i++)
        if (T[i] == '1') Y = (Y + i) % P;
    int e = (X - Y + P) % P;
    if (e > n) D = P - e;
    else D = e;
    cout << D << endl;
    return 0;
}

加强版

由 01 串不难想到异或。把 Hash 函数改为「所有 $\texttt{1}$ 的位置编号之异或和」就能过了。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string S;
    cin >> S;
    int X = 0;
    int n = S.size();
    S = ' ' + S;
    for (int i = 1; i <= n; i++)
        if (S[i] == '1') X ^= i;
    cout << X << endl;
    return 0;
}

/* ATTENTION!!! THIS IS THE BARRIER!!! */

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string T;
    int X;
    cin >> T >> X;
    int D = 0;
    int n = T.size();
    T = ' ' + T;
    for (int i = 1; i <= n; i++)
        if (T[i] == '1') X ^= i;
    D = X;
    cout << D << endl;
    return 0;
}