对拍
🏪

对拍

Tags
杂项
对拍
Last Updated
Last updated May 14, 2022
Author
Created
Oct 15, 2020 12:58 PM
Featured
Featured
Slug
当你找到了一道好题,却没有数据,也无法提交,但是却又标程或暴力一份,想验证自己的程序是否正确,这时,你就需要对拍了。

环境

Ubuntu 16.04
GCC 9.3.0
注:本文在Linux下适用,Windows下如果要使用请安装WSL(我的Ubuntu就是WSL)或Bash for windows(没试过),Mac应该差不多(吧)
 

开始

本文以这样一个问题为例:输入个数,并求和输出。
先准备两种(看似)不一样的解法(都不需要文件输入输出):
第一个命名为(意思是暴力):
//File: bf.cpp //Author: yanyanlongxia //Date: 2020/9/21 // #include <bits/stdc++.h> #define int long long using namespace std; int n,sum; signed main() { int x; scanf("%lld",&n); for(int i=1;i<=n;i++) { scanf("%lld",&x); sum+=x; } printf("%lld\n",sum); return 0; }
第二个命名为(意思是正解/标程,也可以是自己写的不确定解法):
//File: std.cpp //Author: yanyanlongxia //Date: 2020/9/21 // #include <bits/stdc++.h> #define int long long using namespace std; int n,a[10000005],sum; signed main() { scanf("%lld",&n); for (int i=1;i<=n;i++) scanf("%lld",&a[i]); for (int i=1;i<=n;i++) sum+=a[i]; printf("%lld\n",sum); return 0; }
还要准备一个(就是数据生成器,也不要文件输出):
//File: maker.cpp //Author: yanyanlongxia //Date: 2020/9/21 // #include <bits/stdc++.h> #define int long long using namespace std; int random(int n) { return rand()*rand()%n; } signed main() { srand(time(0)); int n=random(10000000)+1; int m=1000000000; printf("%lld\n",n); for (int i=1;i<=n;i++) printf("%lld\n",random(2*m+1)-m); return 0; }
注:之所以自己写一个函数是因为根据系统有Rand_max上限,很多大数无法生成。(还有其他的一些数据生成程序会放在文末)
把以上三个文件放到同一目录下,并编译(可以不运行)。

对拍

这里,我们写一段脚本,网上还有用的,但是我个人认为最好写。
先附上代码,在慢慢解释:
#!/bin/bash for i in {1..100} ; do ./maker > tmp.in time ./bf < tmp.in > bf.out time ./std < tmp.in > std.out if diff bf.out std.out ; then printf "Accepted\n" else printf "Wrong Answer\n" exit 0; fi sleep 0.5s done
第一行申明解释器,即为bash(不加可能会显示file not found之类的错误)。
第二行就是一个循环,从1到100
./maker是Linux下C++的编译结果,tmp.in是要写入的文件
time函数是计时用的,方便查看程序是否超时。尖括号内是输入文件,后面是输出文件
diff就是比较
if ; then dosomething…… else dosomething…… fi
这时if语句的固定结构,分号前的是条件,fi是结尾,表示停止if语句,和while后的done有点相似(感觉好草率)
sleep后的时间可以自己修改,方便查看时间。
最后,将这个脚本命名为,并放入前三个程序所在的文件夹
在终端中cd 到该文件夹,输入 ./checker.sh
如需root权限,在前面加上sudo即可

结果

 

附录

已有数据对拍验证

#!/bin/bash i=1 while [ $i -le 20 ]; do echo test $i time ./file<file$i.in>file.out if diff file.out file$i.out; then echo AC else echo WA exit 0 fi i=$(($i+1)) done
其中,file替换为文件前缀,可以把20换为数据组数。