QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#624576#4234. Tic Tac Toe CountingNYCU_CartesianTree#WA 24ms5144kbC++142.9kb2024-10-09 16:09:352024-10-09 16:09:36

Judging History

This is the latest submission verdict.

  • [2024-10-09 16:09:36]
  • Judged
  • Verdict: WA
  • Time: 24ms
  • Memory: 5144kb
  • [2024-10-09 16:09:35]
  • Submitted

answer

//============================================================================
// Name        : J.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pb push_back

vector<vector<char>> a(4), tot(4);

int num=0, ans1=0, ans2=0;

bool win(){
	for(int i=1;i<=3;i++){
		set<char>t;
		for(int j=1;j<=3;j++) t.insert(a[i][j]);
		if(t.size()==1){
			if(*t.begin()=='O') return 2;
			else if(*t.begin()=='X') return 1;
		}
	}
	for(int i=1;i<=3;i++){
		set<char>t;
		for(int j=1;j<=3;j++) t.insert(a[j][i]);
		if(t.size()==1){
			if(*t.begin()=='O') return 2;
			else if(*t.begin()=='X') return 1;
		}
	}
	{
		set<char>t;
		t.insert(a[1][1]);
		t.insert(a[2][2]);
		t.insert(a[3][3]);
		if(t.size()==1){
			if(*t.begin()=='O') return 2;
			else if(*t.begin()=='X') return 1;
		}
	}
	{
		set<char>t;
		t.insert(a[1][3]);
		t.insert(a[2][2]);
		t.insert(a[3][1]);
		if(t.size()==1){
			if(*t.begin()=='O') return 2;
			else if(*t.begin()=='X') return 1;
		}
	}
	return 0;
}
bool ok=0;

map<vector<vector<char> >, pair<int, int> > ans;

void dfs(int t){
	if(ans.find(a) != ans.end()){
		return;
	}

	ans[a] = {0, 0};
	auto &p = ans[a];
	int ww = win();
	if(ww){

		if(t % 2 == 1){
			p.second++;
		}else{
			p.first++;
		}
		return;
	}
	if(t == 10)
		return;
//	for(int i = 1; i <= 3; i++){
//		for(int j = 1; j <= 3; j++){
//			cerr << a[i][j];
//		}
//		cerr << '\n';
//	}
	char now = (t % 2) ? 'X' : 'O';
	for(int i = 1; i <= 3; i++){
		for(int j = 1; j <= 3; j++){
			if(a[i][j] == '.'){
				a[i][j] = now;
				dfs(t + 1);
				p.first += ans[a].first;
				p.second += ans[a].second;
				a[i][j] = '.';
			}
		}
	}
}

//
//
//void go(int t){
//	if(t-1==num){
//		if(!eq()) return;
//		ok=1;
//	}
//
//	int ww=win();
//	if(ww){
//		if(t-1<num) return;
//		if(ww==1) ans1++;
//		else ans2++;
//		return;
//	}
//	if(t==10) return;
//	char now='O';
//	if(t%2) now='X';
//	for(int i=1;i<=3;i++){
//		for(int j=1;j<=3;j++){
//			if(a[i][j]=='.'){
//				a[i][j]=now;
//				go(t+1);
//				a[i][j]='.';
//			}
//		}
//	}
//
//}

void solve(){

	string aa;
	cin>>aa;
	int x=1, y=1;
	for(auto t: aa){
		tot[x][y]=t;
		y++;
		if(y == 4){
			y = 1;
			x++;
		}
	}
	if(ans.find(tot) != ans.end()){
		auto &p = ans[tot];
		cout << p.first << ' ' << p.second << '\n';
	}else{
		cout << -1 << '\n';
	}

}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);
	for(int i=1;i<=3;i++) {
		a[i].resize(4);
		tot[i].resize(4);
		for(int j=1;j<=3;j++) a[i][j]='.';
	}
	dfs(1);
	int t;
	cin>>t;
	while(t--)
		solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 24ms
memory: 5144kb

input:

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

output:

191 194
232 200
0 1
-1

result:

wrong answer 4th lines differ - expected: '-1 -1', found: '-1'