QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#348994#4234. Tic Tac Toe CountingLaStataleBlue#WA 54ms4428kbC++232.1kb2024-03-09 22:51:142024-03-09 22:51:14

Judging History

This is the latest submission verdict.

  • [2024-03-09 22:51:14]
  • Judged
  • Verdict: WA
  • Time: 54ms
  • Memory: 4428kb
  • [2024-03-09 22:51:14]
  • Submitted

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'