QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#348994 | #4234. Tic Tac Toe Counting | LaStataleBlue# | WA | 54ms | 4428kb | C++23 | 2.1kb | 2024-03-09 22:51:14 | 2024-03-09 22:51:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
map<string,pair<int,int>> memo;
void solve([[maybe_unused]] int t){
string s;
cin>>s;
const vector<array<int,3>> pos = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{6,4,2}};
auto win = [&](string ss,char c)->bool{
for(auto [x,y,z] : pos){
if(ss[x]==c && ss[y]==c && ss[z]==c)return true;
}
return false;
};
if(win(s,'X') && win(s,'O')){
cout<<"-1 -1\n";
return;
}
int contx=0,conto=0;
for(auto i : s)if(i=='X')contx++;else if(i=='O')conto++;
for(auto c : {'X','O'}){
if(win(s,c)){
bool ok=false;
for(int i=0;i<(int)s.size();i++){
if(s[i]!=c)continue;
s[i]='.';
ok|=!win(s,c);
s[i]=c;
}
if(!ok){
cout<<"-1 -1\n";
return;
}
if(c=='O' && !(contx==conto)){
cout<<"-1 -1\n";
return;
}
if(c=='X' && !(contx==conto+1)){
cout<<"-1 -1\n";
return;
}
}
}
auto calc = [&](auto &calc,string s,int turno)->pair<int,int>{
if(memo.find(s)!=memo.end())return memo[s];
if(win(s,'O'))return {0,1};
if(win(s,'X'))return {1,0};
char c = (turno ? 'X' : 'O');
pair<int,int> res;
for(int i=0;i<(int)s.size();i++){
if(s[i]=='.'){
s[i]=c;
auto tmp = calc(calc,s,turno^1);
res.first+=tmp.first;
res.second+=tmp.second;
s[i]='.';
}
}
return memo[s]=res;
};
auto ans = calc(calc,s,contx==conto);
cout<<ans.first<<" "<<ans.second<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
for(int i=1;i<=t;i++)solve(i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3632kb
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: 0
Accepted
time: 32ms
memory: 3908kb
input:
100000 ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......
output:
131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 131184 77904 1...
result:
ok 100000 lines
Test #3:
score: -100
Wrong Answer
time: 54ms
memory: 4428kb
input:
100000 ......... X........ O........ .X....... XX....... OX....... .O....... XO....... OO....... ..X...... X.X...... O.X...... .XX...... XXX...... OXX...... .OX...... XOX...... OOX...... ..O...... X.O...... O.O...... .XO...... XXO...... OXO...... .OO...... XOO...... OOO...... ...X..... X..X..... O.....
output:
131184 77904 14652 7896 3384 16044 14232 10176 1602 1236 1798 1276 5904 16392 2048 756 624 1878 14652 7896 1770 780 1832 1132 1602 1236 -1 -1 220 248 2048 756 268 144 136 316 3384 16044 1832 1132 120 1966 1798 1276 220 248 16 348 624 1878 136 316 -1 -1 14232 10176 1602 1236 1798 1276 1872 1536 286 3...
result:
wrong answer 3rd lines differ - expected: '-1 -1', found: '3384 16044'