博客详情 - Hydro

HHHE 的博客
通信题配置指南
HHHE LV 5 @ 2022-4-7 17:42:21

对于通信题，一般需要提交两个文件，但 Hydro 并不支持，这里实现了一个编译脚本从一个文件中来自动读取两个文件的内容。

具体的，对于提交的文件，应形如

///********** Alice.cpp Begin **********/
#include "Alice.h"
//Your code here
/********** Alice.cpp End **********/
/********** Bob.cpp Begin **********/
#include "Bob.h"
//Your code here
/********** Bob.cpp End **********/

其中， $\texttt{Alice.cpp}$ 是题目中要求提交的第一个文件， $\texttt{Bob.cpp}$ 是第二个文件。

compile.sh 如下

file1="Alice" # 第一个文件名
file2="Bob"   # 第二个文件名
/bin/sed -i "s/\r//g" "foo.cc" # 将 Windows 中的 \r\n 替换成 \n
s1=$(echo -e "/********** $file1.cpp Begin **********/\n")
s2=$(echo -e "/********** $file1.cpp End **********/\n")
s3=$(echo -e "/********** $file2.cpp Begin **********/\n")
s4=$(echo -e "/********** $file2.cpp End **********/\n")
flag=0
while read LINE
do
	if [ $flag -eq 0 ]
    then
		if [ "$LINE" == "$s1" ]
        then
			flag=1
		fi
	elif [ $flag -eq 1 ]
    then
		if [ "$LINE" != "$s2" ]
        then
			echo "$LINE" >> "$file1".cc
		else
            flag=2
		fi
	elif [ $flag -eq 2 ]
    then
		if [ "$LINE" == "$s3" ]
        then
			flag=3
		fi
	elif [ $flag -eq 3 ]
    then
		if [ "$LINE" != "$s4" ]
        then
			echo "$LINE" >> "$file2".cc
		else
            flag=4
		fi
	else
        break
    fi
done < foo.cc # 截取文件
g++ -std=c++14 grader.cc "$file1".cc "$file2".cc -o foo -O2 # 编译

使用时将此文件置入 user_extra_file 中。

但是，这种方法非常容易被卡，包括但不限于使用 extern、在 Alice.cpp 中打开 Bob.h 等，因此，参照 CMS 中的做法，我们应当需要 $3$ 个 grader 文件，其中 $2$ 个与选手程序一起编译，另一个（称为 manager）从标准输入中读取数据，并将结果输出到标准输出中，同时用 $4$ 个管道将它们之间进行通信。

具体的，我们设 $4$ 个管道为 pipe1 pipe2 pipe3 pipe4，将 pipe1 pipe2 分别重定向到第一个文件的标准输入输出，pipe3 pipe4 分别重定向到第二个文件的标准输入输出。同时，在 manager 中，我们从 pipe2 读入第一个文件的通信信息，并将第二个文件的通信信息输出到 pipe1 中，pipe3 pipe4 同理。

以此题（来自 JOISC）为例，我的配置如下

# config.yaml
user_extra_files:
- execute.sh
- compile.sh
- Azer.h
- Azer_grader.cc
- grader.cc
- Baijan.h
- Baijan_grader.cc

# compile.sh
file1="Azer"
file2="Baijan"
/bin/sed -i "s/\r//g" "foo.cc"
s1=$(echo -e "/********** $file1.cpp Begin **********/\n")
s2=$(echo -e "/********** $file1.cpp End **********/\n")
s3=$(echo -e "/********** $file2.cpp Begin **********/\n")
s4=$(echo -e "/********** $file2.cpp End **********/\n")
flag=0
while read LINE
do
	if [ $flag -eq 0 ]
    then
		if [ "$LINE" == "$s1" ]
        then
			flag=1
		fi
	elif [ $flag -eq 1 ]
    then
		if [ "$LINE" != "$s2" ]
        then
			echo "$LINE" >> "$file1".cc
		else
            flag=2
		fi
	elif [ $flag -eq 2 ]
    then
		if [ "$LINE" == "$s3" ]
        then
			flag=3
		fi
	elif [ $flag -eq 3 ]
    then
		if [ "$LINE" != "$s4" ]
        then
			echo "$LINE" >> "$file2".cc
		else
            flag=4
		fi
	else
        break
    fi
done < foo.cc
g++ -std=c++14 "$file1"_grader.cc "$file1".cc -o "$file1" -O2
g++ -std=c++14 "$file2"_grader.cc "$file2".cc -o "$file2" -O2
g++ -std=c++14 grader.cc -o grader -O2 # 分别编译
zip -q foo "$file1" "$file2" grader
/bin/mv foo.zip foo # 由于 Hydro 只识别 foo，故要压缩之后重命名

# execute.sh
unzip foo > /dev/null # 解压
file1="Azer"
file2="Baijan"
mkfifo pipe1 pipe2 pipe3 pipe4 # 创建管道
/bin/rm foo "$file1"_grader.cc "$file2"_grader.cc "$file1".h "$file2".h compile.sh grader.cc execute.sh
./"$file1" pipe2 pipe1 &
./"$file2" pipe4 pipe3 & # 在后台运行，参数相关参见下文
./grader pipe1 pipe2 pipe3 pipe4

这里提一嘴，这里需要将相关文件删掉，不然选手可以在自测中直接 system("/bin/cat xxx") 读取文件。

// Azer_grader.cc
#include <cassert>
#include <cstdio>
#include "Azer.h"
namespace {
	bool q[60000];
	int l = 0, r = 0;
}
void SendA(bool y) {q[++r] = y;}
int main(int argc, char *argv[]) {
	assert(argc == 3);
	FILE *rd = fopen(argv[1], "r"), *wr = fopen(argv[2], "w"); // 顺序不要写反了！
	int N, A;
	assert(fscanf(rd, "%d%d", &N, &A) == 2);
	std::vector<int> U(A), V(A), C(A);
	for (int i = 0; i < A; ++i)
		assert(fscanf(rd, "%d%d%d", &U[i], &V[i], &C[i]) == 3);
	InitA(N, A, U, V, C);
	for (fprintf(wr, "%d\n", r); l < r;)
		fprintf(wr, "%d\n", q[++l]);
	fflush(wr);
	for (int x;;) {
		assert(fscanf(rd, "%d", &x) == 1);
		if (x == 2) break;
		l = r = 0;
		ReceiveA(x);
		for (fprintf(wr, "%d\n", r); l < r;)
			fprintf(wr, "%d\n", q[++l]);
		fflush(wr);
	}
	auto Z = Answer();
	for (int i = 0; i < N; ++i) fprintf(wr, "%d\n", Z[i]);
	fflush(wr);
	return 0;
}

// Baijan_grader.cc
#include <cassert>
#include <cstdio>
#include "Baijan.h"
namespace {
	bool q[60000];
	int l = 0, r = 0;
}
void SendB(bool x) {q[++r] = x;}
int main(int argc, char *argv[]) {
	assert(argc == 3);
	FILE *rd = fopen(argv[1], "r"), *wr = fopen(argv[2], "w"); // 顺序不要写反了！
	int N, B;
	assert(fscanf(rd, "%d%d", &N, &B) == 2);
	std::vector<int> S(B), T(B), D(B);
	for (int j = 0; j < B; ++j)
		assert(fscanf(rd, "%d%d%d", &S[j], &T[j], &D[j]) == 3);
	InitB(N, B, S, T, D);
	for (fprintf(wr, "%d\n", r); l < r;)
		fprintf(wr, "%d\n", q[++l]);
	fflush(wr);
	for (int x;;) {
		assert(fscanf(rd, "%d", &x) == 1);
		if (x == 2) break;
		l = r = 0;
		ReceiveB(x);
		for (fprintf(wr, "%d\n", r); l < r;)
			fprintf(wr, "%d\n", q[++l]);
		fflush(wr);
	}
	return 0;
}

// grader.cc
#include <cassert>
#include <cstdio>
#include <queue>
int main(int argc, char *argv[]) {
	assert(argc == 5);
	FILE *wr1 = fopen(argv[2], "w"), *wr2 = fopen(argv[4], "w");
	FILE *rd1 = fopen(argv[1], "r"), *rd2 = fopen(argv[3], "r"); // 顺序不要写反了！
	int N, A, B, num_calls = 0, nowx, nowy;
	std::queue<bool> qx, qy;
	assert(scanf("%d%d%d", &N, &A, &B) == 3);
	fprintf(wr1, "%d %d\n", N, A);
	fprintf(wr2, "%d %d\n", N, B);
	for (int i = 0, U, V, C; i < A; ++i) {
		assert(scanf("%d%d%d", &U, &V, &C) == 3);
		fprintf(wr1, "%d %d %d\n", U, V, C);
	}
	for (int j = 0, S, T, D; j < B; ++j) {
		assert(scanf("%d%d%d", &S, &T, &D) == 3);
		fprintf(wr2, "%d %d %d\n", S, T, D);
	}
	fflush(wr1);
	fflush(wr2);
	assert(fscanf(rd1, "%d", &nowx) == 1);
	assert(fscanf(rd2, "%d", &nowy) == 1);
	for (int x;; ) {
		while (nowx--) {
			assert(fscanf(rd1, "%d", &x) == 1);
			if (++num_calls > 58000)
				return printf("Wrong Answer\n"), 0;
			qy.push(x);
		}
		while (nowy--) {
			assert(fscanf(rd2, "%d", &x) == 1);
			if (++num_calls > 58000)
				return printf("Wrong Answer\n"), 0;
			qx.push(x);
		}
		nowx = nowy = 0;
		if (!qx.empty()) {
			fprintf(wr1, "%d\n", qx.front());
			fflush(wr1);
			assert(fscanf(rd1, "%d", &nowx) == 1);
			qx.pop();
		} else if (!qy.empty()) {
			fprintf(wr2, "%d\n", qy.front());
			fflush(wr2);
			assert(fscanf(rd2, "%d", &nowy) == 1);
			qy.pop();
		} else break;
	}
	fprintf(wr1, "2\n");
	fflush(wr1);
	fprintf(wr2, "2\n");
	fflush(wr2);
	fprintf(stderr, "Accepted, L = %d\n", num_calls);
	for (int i = 0, Z; i < N; ++i) {
		assert(fscanf(rd1, "%d", &Z) == 1);
		printf("%d\n", Z);
	}
	return 0;
}

下面文件全部蒯自官方

// Azer.h
#include <vector>

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C);
void ReceiveA(bool x);
std::vector<int> Answer();

void SendA(bool y);

// Baijan.h
#include <vector>

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D);
void ReceiveB(bool y);

void SendB(bool x);

// foo.cc
/********** Azer.cpp Begin **********/
#include "Azer.h"
#include <queue>

using namespace std;

namespace {

const int INF = 1000000007;

int n;
vector<pair<int, int> > *E;
vector<int> dist;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > PQ;
int Lcnt;
int Mcnt;
int buf;
bool mode;
int dist_m;
int d_sent;

void updateQ(int N) {
	for(auto e: E[N]) {
		if(dist[N] + e.second < -dist[e.first]) {
			dist[e.first] = -(dist[N] + e.second);
			PQ.push(make_pair(dist[N] + e.second, e.first));
		}
	}
}

void getQ() {
	if(Lcnt == 0) return;
	Lcnt--;
	for(;;) {
		if(PQ.empty()) {
			d_sent = (1 << 9) - 1;
			for(int i = 8; i >= 0; i--) {
				SendA((d_sent >> i) & 1);
			}
			return;
		}
		pair<int, int> rem = PQ.top();
		if(rem.first + dist[rem.second] == 0) {
			d_sent = rem.first - dist_m;
			for(int i = 8; i >= 0; i--) {
				SendA((d_sent >> i) & 1);
			}
			return;
		}
		PQ.pop();
	}
}

} // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) {
	n = N;
	E = new vector<pair<int, int> >[N];
	for(int i = 0; i < A; i++) {
		E[U[i]].push_back(make_pair(V[i], C[i]));
		E[V[i]].push_back(make_pair(U[i], C[i]));
	}
	dist.push_back(0);
	for(int i = 1; i < N; i++) {
		dist.push_back(-INF);
	}
	Lcnt = N - 1;
	dist_m = 0;
	updateQ(0);
	getQ();
	mode = false;
	Mcnt = 0;
	buf = 0;
}

void ReceiveA(bool x) {
	buf *= 2;
	buf += x;
	if(mode) {
		if(++Mcnt == 11) {
			dist_m += d_sent;
			dist[buf] = dist_m;
			updateQ(buf);
			getQ();
			mode = false;
			Mcnt = 0;
			buf = 0;
		}
	} else {
		if(++Mcnt == 9) {
			if(buf >= d_sent) {
				int N = PQ.top().second;
				for(int i = 10; i >= 0; i--) {
					SendA((N >> i) & 1);
				}
				dist_m += d_sent;
				dist[N] = dist_m;
				updateQ(N);
				getQ();
			} else {
				d_sent = buf;
				mode = true;
			}
			Mcnt = 0;
			buf = 0;
		}
	}
}

std::vector<int> Answer() {
	return dist;
}
/********** Azer.cpp End **********/
/********** Baijan.cpp Begin **********/
#include "Baijan.h"
#include <queue>

using namespace std;

namespace {

const int INF = 1000000007;
int n;
vector<pair<int, int> > *E;
vector<int> dist;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > PQ;
int Lcnt;
int Mcnt;
int buf;
bool mode;
int dist_m;
int d_sent;

void updateQ(int N) {
	for(auto e: E[N]) {
		if(dist[N] + e.second < -dist[e.first]) {
			dist[e.first] = -(dist[N] + e.second);
			PQ.push(make_pair(dist[N] + e.second, e.first));
		}
	}
}

void getQ() {
	if(Lcnt == 0) return;
	Lcnt--;
	for(;;) {
		if(PQ.empty()) {
			d_sent = (1 << 9) - 1;
			for(int i = 8; i >= 0; i--) {
				SendB((d_sent >> i) & 1);
			}
			return;
		}
		pair<int, int> rem = PQ.top();
		if(rem.first + dist[rem.second] == 0) {
			d_sent = rem.first - dist_m;
			for(int i = 8; i >= 0; i--) {
				SendB((d_sent >> i) & 1);
			}
			return;
		}
		PQ.pop();
	}
}

} // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) {
	n = N;
	E = new vector<pair<int, int> >[N];
	for(int i = 0; i < B; i++) {
		E[S[i]].push_back(make_pair(T[i], D[i]));
		E[T[i]].push_back(make_pair(S[i], D[i]));
	}
	dist.push_back(0);
	for(int i = 1; i < N; i++) {
		dist.push_back(-INF);
	}
	Lcnt = N - 1;
	dist_m = 0;
	updateQ(0);
	getQ();
	mode = false;
	Mcnt = 0;
	buf = 0;
}

void ReceiveB(bool y) {
	buf *= 2;
	buf += y;
	if(mode) {
		if(++Mcnt == 11) {
			dist_m += d_sent;
			dist[buf] = dist_m;
			updateQ(buf);
			getQ();
			mode = false;
			Mcnt = 0;
			buf = 0;
		}
	} else {
		if(++Mcnt == 9) {
			if(buf > d_sent) {
				int N = PQ.top().second;
				for(int i = 10; i >= 0; i--) {
					SendB((N >> i) & 1);
				}
				dist_m += d_sent;
				dist[N] = dist_m;
				updateQ(N);
				getQ();
			} else {
				d_sent = buf;
				mode = true;
			}
			Mcnt = 0;
			buf = 0;
		}
	}
}
/********** Baijan.cpp End **********/

值得一提的是，由于 flush 次数过多，导致常数极大，这里请教一下有没有可以减少常数的办法。（原题时限 1s，我这个要跑 2s+）。

通信题配置指南

状态

开发

支持

通信题配置指南

状态

开发

支持

还没有账户？

登录