QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54526#4234. Tic Tac Toe CountingYL1F4#WA 332ms4156kbC++141.4kb2022-10-09 15:31:212022-10-09 15:31:22

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-09 15:31:22]
  • Judged
  • Verdict: WA
  • Time: 332ms
  • Memory: 4156kb
  • [2022-10-09 15:31:21]
  • Submitted

answer

#include<iostream>
#include<string>
#include<map>
#include<utility>
#include<cstdio>
std::map<std::string,std::pair<int,int>>dp;
char chkwin(std::string s){
	if(s[0]==s[1]&&s[1]==s[2]){
		return s[0];
	}
	if(s[3]==s[4]&&s[4]==s[5]){
		return s[3];
	}
	if(s[6]==s[7]&&s[7]==s[8]){
		return s[6];
	}
	if(s[0]==s[3]&&s[3]==s[6]){
		return s[0];
	}
	if(s[1]==s[4]&&s[4]==s[7]){
		return s[1];
	}
	if(s[2]==s[5]&&s[5]==s[8]){
		return s[2];
	}
	if(s[0]==s[4]&&s[4]==s[8]){
		return s[0];
	}
	if(s[2]==s[4]&&s[4]==s[6]){
		return s[2];
	}
	return '.';
}
std::pair<int,int>add(std::pair<int,int>a,std::pair<int,int>b){
	return std::make_pair(a.first+b.first,a.second+b.second);
}
std::pair<int,int> dfs(std::string s,char q){
	if(dp.count(s)){
		return dp[s];
	}
//	std::cout<<s<<std::endl;
	if(chkwin(s)==(q=='X'?'O':'X')){
//		std::cout<<":fck"<<" "<<s<<" "<<chkwin(s)<<std::endl;
		if(q=='X'){
			dp[s]=std::make_pair(1,0);
		}else{
			dp[s]=std::make_pair(0,1);
		}
		return dp[s];
	}
	for(int i=0;i<9;i++){
		if(s[i]=='.'){
			auto tmp=s;
			tmp[i]=q;
			dp[s]=add(dp[s],dfs(tmp,(q=='X'?'O':'X')));
		}
	}
	return dp[s];
}
int main(){
	dfs(".........",'X');
	int T;scanf("%d",&T);
	while(T--){
		std::string s;
		std::cin>>s;
		if(!dp.count(s)){
			puts("-1 -1");
		}else{
			printf("%d %d\n",dp[s].second,dp[s].first);
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 9ms
memory: 4156kb

input:

4
XX..O....
X...OX...
OOOX.X.X.
OOOXXX...

output:

191 194
232 200
0 1
-1 -1

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 332ms
memory: 4100kb

input:

100000
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
.........
......

output:

133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
133128 78408
1...

result:

wrong answer 1st lines differ - expected: '131184 77904', found: '133128 78408'