QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#810443#7970. 三步棋GeekmenAC ✓1ms3600kbC++142.2kb2024-12-11 22:38:112024-12-11 22:38:12

Judging History

This is the latest submission verdict.

  • [2024-12-11 22:38:12]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3600kb
  • [2024-12-11 22:38:11]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

namespace pattern {
	char dp[1 << 25];
	vector<pair<int, int>> d;
	
	int code(int i, int j) {
		return i * 5 + j;
	}
	char DP(int gr, int step) {
		if (dp[gr]) return dp[gr];
		
		auto out = [&](int x, int y) -> bool {
			return x < 0 || y < 0 || x > 4 || y > 4 || !(gr >> code(x, y) & 1);
		};
		auto sc = gr;
		dp[sc] = 2;
		for (int i = 0; i < 5; i ++)
			for (int j = 0; j < 5; j ++) {
				if (gr >> code(i, j) & 1) continue;
				gr ^= (1 << code(i, j));
				bool match = 0;
				for (int ch = 0; ch < d.size(); ch ++) {
					int ok = 1, sx = i - d[ch].first, sy = j - d[ch].second;
					for (int k = 0; k < d.size(); k ++)
						if (out(sx + d[k].first, sy + d[k].second)) {
							ok = 0;
							break;
						}
					if (ok) {
						if ((step + 1) % 3 == 0) return dp[sc] = 1;
						match = 1;
						break;
					}
				}
				if (!match && DP(gr, step + 1) == 2) return dp[sc] = 1;
				gr ^= (1 << code(i, j));
			}
		return 2;
	}
	
	void solve() {
		memset(dp, 0, sizeof dp);
		d.clear();
		vector<vector<char>> gr(5, vector<char>(5));
		int x = -1, y;
		for (int i = 0; i < 5; i ++)
			for (int j = 0; j < 5; j ++) {
				cin >> gr[i][j];
				if (gr[i][j] == 'o') {
					if (x == -1) x = i, y = j;
					d.push_back({i - x, j - y});
				}
			}
		
		if (DP(0, 0) == 1) cout << "Far" << endl;
		else cout << "Away" << endl; 
	}
}
namespace std {
	void solve() {
		int mnx = 5, mny = 5, mxx = -1, mxy = -1, cnt = 0;
		for (int i = 0; i < 5; i ++)
			for (int j = 0; j < 5; j ++) {
				char x;
				cin >> x;
				if (x == 'o') {
					mnx = min(mnx, i), mny = min(mny, j);
					mxx = max(mxx, i), mxy = max(mxy, j);
					cnt ++;
				}
			}
		
		if (cnt == 1) cout << "Away" << endl;
		else if (cnt == 2) cout << "Far" << endl;
		else if (cnt == 3) cout << "Away" << endl;
		else {
			if ((mxx - mnx + 1) * (mxy - mny + 1) == cnt) cout << "Away" << endl;
			else cout << "Far" << endl;
		}
	}
}

int main() {
	int T;
	cin >> T;
	
	while (T -- ) std::solve();
}
/*
1
oooo.
.....
.....
.....
.....
Away

1
...o.
.ooo.
.....
.....
.....
Far

1
...oo
...oo
.....
.....
.....
Away

1
..o..
.ooo.
.....
.....
.....
Far
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 3600kb

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