QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#286979#7970. 三步棋iteraterAC ✓107ms353324kbC++143.6kb2023-12-19 10:20:382023-12-19 10:20:38

Judging History

This is the latest submission verdict.

  • [2023-12-19 10:20:38]
  • Judged
  • Verdict: AC
  • Time: 107ms
  • Memory: 353324kb
  • [2023-12-19 10:20:38]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 25);
int bitcount[N];
struct grid { bool a[5][5]; } Empty, x;
char s[5][5];
vector < pair <int, int> > pattern;
int caseID, dfn[N], patternDfn[N];
bool f[N], g[N];
bool hasPattern(int s)
{
	if (patternDfn[s] == caseID) return g[s];
	patternDfn[s] = caseID;
	for (int i = 0; i < 5; i++)
	for (int j = 0; j < 5; j++)
	if (x.a[i][j])
	{
		bool valid = 1;
		for (auto cur : pattern)
		{
			int di = cur.first, dj = cur.second;
			int pi = i + di, pj = j + dj;
			if (pi < 0 || pi > 4 || pj < 0 || pj > 4) { valid = 0; break; }
			if (!x.a[pi][pj]) { valid = 0; break; }
		}
		if (valid) return g[s] = 1;
	}
	return g[s] = 0;
}
int sum;
bool dfs(int s)
{
	if (hasPattern(s))
	{
		if (bitcount[s] % 3 == 0) return 0;
		else return 1;
	}
	if (dfn[s] == caseID) return f[s];
	dfn[s] = caseID;
	for (int i = 0; i < 5; i++)
	for (int j = 0; j < 5; j++)
	{
		if (x.a[i][j]) continue;
		x.a[i][j] = 1;
		bool res = dfs(s + (1 << (i * 5 + j)));
		x.a[i][j] = 0;
		if (!res) return f[s] = 1;
	}
	return f[s] = 0;
}
map < vector < pair <int, int> >, bool> h;
vector < pair <int, int> > trans(vector < pair <int, int> > v)
{
	for (int i = 0; i < (int) v.size(); i++) swap(v[i].first, v[i].second);
	sort(v.begin(), v.end());
	for (int i = (int) v.size() - 1; i >= 0; i--) v[i] = make_pair(v[i].first - v[0].first, v[i].second - v[0].second);
	return v;
}
vector < pair <int, int> > reflectx(vector < pair <int, int> > v)
{
	for (int i = 0; i < (int) v.size(); i++) v[i] = make_pair(4 - v[i].first, v[i].second);
	sort(v.begin(), v.end());
	for (int i = (int) v.size() - 1; i >= 0; i--) v[i] = make_pair(v[i].first - v[0].first, v[i].second - v[0].second);
	return v;
}
vector < pair <int, int> > reflecty(vector < pair <int, int> > v)
{
	for (int i = 0; i < (int) v.size(); i++) v[i] = make_pair(v[i].first, 4 - v[i].second);
	sort(v.begin(), v.end());
	for (int i = (int) v.size() - 1; i >= 0; i--) v[i] = make_pair(v[i].first - v[0].first, v[i].second - v[0].second);
	return v;
}
void update(vector < pair <int, int> > v, bool s)
{
	if (h.count(v)) return;
	h[v] = s;
	update(trans(v), s); update(reflectx(v), s); update(reflecty(v), s);
}
void makeTable()
{
	pattern.clear(); pattern = { make_pair(0, 0), make_pair(0, 1), make_pair(0, 2), make_pair(0, 3) }; update(pattern, 0);
	pattern.clear(); pattern = { make_pair(0, 0), make_pair(1, -2), make_pair(1, -1), make_pair(1, 0) }; update(pattern, 1);
	pattern.clear(); pattern = { make_pair(0, 0), make_pair(1, -1), make_pair(1, 0), make_pair(1, 1) }; update(pattern, 1);
	pattern.clear(); pattern = { make_pair(0, 0), make_pair(0, 1), make_pair(1, 0), make_pair(1, 1) }; update(pattern, 0);
	pattern.clear(); pattern = { make_pair(0, 0), make_pair(1, 0), make_pair(1, 1), make_pair(2, 1) }; update(pattern, 1);
}
void solve()
{
	for (int i = 0; i < 5; i++) scanf("%s", s[i]);
	pattern.clear();
	for (int i = 0; i < 5 && pattern.empty(); i++)
	for (int j = 0; j < 5 && pattern.empty(); j++)
	if (s[i][j] == 'o')
	{
		for (int pi = 0; pi < 5; pi++)
		for (int pj = 0; pj < 5; pj++)
		if (s[pi][pj] == 'o') pattern.push_back(make_pair(pi - i, pj - j));
	}
	sort(pattern.begin(), pattern.end());
	if (!h.count(pattern)) { assert((int) pattern.size() < 4); x = Empty; update(pattern, dfs(0)); }
	if (h[pattern]) puts("Far");
	else puts("Away");
}
int main()
{
	for (int i = 1; i < N; i++) bitcount[i] = bitcount[i >> 1] + (i & 1);
	makeTable();
	int T;
	scanf("%d", &T);
	for (caseID = 1; caseID <= T; caseID++) solve(); 
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 107ms
memory: 353324kb

input:

200
.....
..oo.
.....
.....
.....
.....
.....
oo...
o....
.....
.....
.o...
oo...
.....
.....
.....
.....
o....
oo...
.....
.....
...o.
..oo.
.....
.....
.....
....o
.....
.....
.....
.....
.....
.....
.ooo.
.o...
.....
.....
.....
.....
...oo
.o...
.o...
.o...
.....
.....
.....
.....
..oo.
.....
.....

output:

Far
Away
Away
Away
Away
Away
Far
Far
Away
Far
Away
Far
Far
Away
Far
Away
Far
Away
Away
Away
Far
Away
Far
Away
Away
Away
Away
Far
Far
Far
Far
Away
Far
Away
Far
Away
Far
Away
Away
Far
Away
Away
Far
Far
Away
Far
Far
Away
Far
Away
Away
Away
Away
Away
Away
Far
Away
Far
Away
Away
Away
Away
Far
Away
Far
Fa...

result:

ok 200 lines

Test #2:

score: 0
Accepted
time: 19ms
memory: 134984kb

input:

200
...oo
..oo.
.....
.....
.....
.....
..ooo
....o
.....
.....
.....
o....
oo...
.o...
.....
.....
.ooo.
...o.
.....
.....
.....
.oo..
..oo.
.....
.....
.....
...o.
...o.
...o.
...o.
.....
.oo..
..o..
..o..
.....
..o..
..ooo
.....
.....
.....
.....
.oooo
.....
.....
.....
.....
.....
o....
oo...
o....

output:

Far
Far
Far
Far
Far
Away
Far
Far
Away
Far
Far
Far
Far
Away
Far
Far
Far
Far
Far
Far
Far
Far
Far
Far
Far
Away
Far
Far
Far
Far
Away
Far
Away
Far
Far
Far
Away
Far
Far
Far
Far
Far
Far
Far
Far
Away
Far
Far
Far
Far
Far
Far
Away
Far
Away
Far
Far
Far
Away
Away
Far
Far
Far
Far
Away
Far
Far
Far
Far
Far
Far
Far...

result:

ok 200 lines