QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#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;
}

Details

Tip: Click on the bar to expand more detailed information

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'