- HHHE 的博客
通信题配置指南
- 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 **********/
其中, 是题目中要求提交的第一个文件, 是第二个文件。
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 中的做法,我们应当需要 个 grader 文件,其中 个与选手程序一起编译,另一个(称为 manager
)从标准输入中读取数据,并将结果输出到标准输出中,同时用 个管道将它们之间进行通信。
具体的,我们设 个管道为 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+)。