QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352829#4234. Tic Tac Toe CountingPetroTarnavskyi#WA 38ms4248kbC++201.8kb2024-03-13 17:10:562024-03-13 17:10:56

Judging History

This is the latest submission verdict.

  • [2024-03-13 17:10:56]
  • Judged
  • Verdict: WA
  • Time: 38ms
  • Memory: 4248kb
  • [2024-03-13 17:10:56]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;


int cntW(string& s)
{
	set<char> winner;
	FOR (i, 0, 3)
	{
		if (s[3 * i] == s[3 * i + 1] && s[3 * i + 1] == s[3 * i + 2])
			winner.insert(s[3 * i]);
		if (s[i] == s[i + 3] && s[i + 3] == s[i + 6])
			winner.insert(s[i]);
	}
	if (s[0] == s[4] && s[4] == s[8])
		winner.insert(s[0]);
	if (s[2] == s[4] && s[4] == s[6])
		winner.insert(s[2]);
	winner.erase('.');
	return SZ(winner);
}

bool valid(string s)
{
	int cntx = 0, cnto = 0;
	FOR (i, 0, SZ(s))
	{
		if (s[i] == 'X')
			cntx++;
		if (s[i] == 'O')
			cnto++;
	}
	if (cntx > cnto + 1 || cnto > cntx)
		return false;
	if (cntW(s) == 2)
		return false;
	return true;
}

map<string, PII> dp;

PII f(string s, int cnt)
{
	if (dp.count(s))
		return dp[s];
	if (cntW(s))
	{
		int x = cnt & 1;
		dp[s] = {x, x ^ 1};
		return dp[s];
	}
	if (cnt == 9)
		return {0, 0};
	PII p = {0, 0};
	FOR (i, 0, SZ(s))
	{
		if (s[i] == '.')
		{
			s[i] = cnt & 1 ? 'O' : 'X';
			auto p2 = f(s, cnt + 1);
			p.F += p2.F;
			p.S += p2.S;
			s[i] = '.';
		}
	}
	dp[s] = p;
	return dp[s];
}

void solve()
{
	string s;
	cin >> s;
	if (!valid(s))
	{
		cout << "-1 -1\n";
		return;
	}
	int cnt = 0;
	FOR (i, 0, 9)
		cnt += s[i] != '.';
	auto p = f(s, cnt);
	cout << p.F << ' ' << p.S << '\n';
	
}

int main()
{	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3540kb

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: 38ms
memory: 4248kb

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: 25ms
memory: 4240kb

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
-1 -1
14232 10176
-1 -1
1798 1276
-1 -1
2048 756
-1 -1
14652 7896
-1 -1
1832 1132
-1 -1
-1 -1
220 248
2048 756
268 144
-1 -1
-1 -1
1832 1132
-1 -1
1798 1276
220 248
-1 -1
-1 -1
-1 -1
-1 -1
14232 10176
-1 -1
1798 1276
-1 -1
-1 -1
264 188
1868 1080
239 126
-1 -1
-1 -1
-1 -1
312...

result:

wrong answer 882nd lines differ - expected: '-1 -1', found: '0 1'