QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54526 | #4234. Tic Tac Toe Counting | YL1F4# | WA | 332ms | 4156kb | C++14 | 1.4kb | 2022-10-09 15:31:21 | 2022-10-09 15:31:22 |
Judging History
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'