QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#300844#7970. 三步棋defyers#AC ✓1ms3508kbC++204.9kb2024-01-08 21:46:202024-01-08 21:46:21

Judging History

This is the latest submission verdict.

  • [2024-01-08 21:46:21]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3508kb
  • [2024-01-08 21:46:20]
  • Submitted

answer

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

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using ll = long long;
using LL = long long;

int dx[5] = {0, -1, 0, 0, 1};
int dy[5] = {0, 0, -1, 1, 0};

bool ok[1 << 25], vis2[1 << 25];

int check(int x) {
	vector<int> dsu(25);
	iota(dsu.begin(), dsu.end(), 0);

	auto find = [&](auto && find, int x) {
		if (dsu[x] == x) return x;
		else return dsu[x] = find(find, dsu[x]);
	};

	vector<string> s(5);
	for (int i = 0; i < 5; i++) {
		s[i] = ".....";
		for (int j = 0; j < 5; j++) {
			if (x >> (i * 5 + j) & 1) {
				s[i][j] = 'o';			
			}
		}
	}

	bool _ok = false;
	for(int i = 0; i < 5; i++){
		if(s[0][i] == 'o') _ok = true;
	}
	if(!_ok) return -1;
	_ok = false;
	for(int i = 0; i < 5; i++){
		if(s[i][0] == 'o') _ok = true;
	}
	if(!_ok) return -1;

	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if (s[i][j] != 'o') continue;
			for (int d = 1; d <= 4; d++) {
				int x = i + dx[d];
				int y = j + dy[d];

				if (x < 0 || x >= 5 || y < 0 || y >= 5 || s[i][j] != 'o' || s[x][y] != 'o') continue;

				int id1 = i * 5 + j;
				int id2 = x * 5 + y;

				dsu[find(find, id1)] = find(find, id2);
			}
		}
	}

	int par = -1;
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {
			if (s[i][j] == 'o') {
				if (par == -1) {
					par = find(find, i * 5 + j);
				}
				else {
					if (find(find, i * 5 + j) != par) {
						return -1;
					}
				}
			}
		}
	}

	int C = 0;
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 5; j++) {

			if (i < 4 && j < 4) {
				if (s[i][j] == 'o' && s[i + 1][j] == 'o' && s[i][j + 1] == 'o' && s[i + 1][j + 1] == 'o') {
					return 0;
					cout << "Away\n";
					// return;
				}
			}

			if (s[i][j] == 'o') ++C;
		}
	}

	vector<int> v;

	for (int ox = -4; ox <= 4; ox++) {
		for (int oy = -4; oy <= 4; oy++) {
			int state = 0;
			int cnt = 0;
			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < 5; j++) {
					int x = ox + i;
					int y = oy + j;
					if (x >= 0 && x < 5 && y >= 0 && y < 5 && s[x][y] == 'o') {
						++cnt;
						state = state | (1 << (i * 5 + j));
					} 
				}
			}
			if (cnt == C) {
				// cout << "@" << cnt << " " << C << " " << state << endl;
				v.push_back(state);
			}
		}
	}

	vector<int> rmv;

	auto dfs2 = [&](auto &&dfs2, int state, int cnt) -> bool {
		if (vis2[state]) {
			return ok[state];
		}

		bool matched = false;

		for (auto x: v) {
			if ((state & x) == x) {
				// cout << "!" << state << " " << x << endl;
				// for (int i = 0; i < 5; i++) {
				// 	for (int j = 0; j < 5; j++) {
				// 		int id = i * 5 + j;
				// 		if ((state >> id) & 1) {
				// 			cout << 'o';
				// 		}
				// 		else {
				// 			cout << '.';
				// 		}
				// 	}
				// 	cout << "\n";
				// }
				bool ret = (cnt % 3 != 0);
				rmv.push_back(state);
				vis2[state] = true;
				ok[state] = ret;
				return ret;
			}
		}

		bool ret = false;
		for (int i = 0; i < 25; i++) {
			if ((state >> i) & 1) {
			}
			else {
				if (!dfs2(dfs2, state | (1 << i), cnt + 1)) {
					ret = true;
					break;
				}
			}
		}

		rmv.push_back(state);
		vis2[state] = true;
		ok[state] = ret;
		return ret;		
	};

	dfs2(dfs2, 0, 0);

	for (auto x: rmv) {
		vis2[x] = false;
	}

	if (ok[0]) {
		return 1;
		cout << "Far\n";
	}
	else {
		return 0;
		cout << "Away\n";
	}
}

map<int, bool> M;

void solve(int TC) {
	vector<string> s(5);
	for (int i = 0; i < 5; i++) {
		cin >> s[i];
	}

	int dx = 5, dy = 5;
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < 5; j++){
			if(s[i][j] == 'o'){
				dx = min(dx, i);
				dy = min(dy, j);
			}
		}
	}

	char t[5][5];
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < 5; j++){
			t[i][j] = '.';
		}
	}
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < 5; j++){
			if(i >= dx && j >= dy){
				t[i - dx][j - dy] = s[i][j];
			}
		}
	}

	int msk = 0;
	for(int i = 0; i < 5; i++){
		for(int j = 0; j < 5; j++){
			msk |= (t[i][j] == 'o') << (i * 5 + j);
		}
	}
	// cout << msk << endl;
	cout << (M[msk] ? "Far\n" : "Away\n");
}

void gen() {
	for (int i = 1; i < (1 << 25); i++) {
		bitset<25> bs(i);
		if (bs.count() <= 4) {
			int ret = check(i);
			if (ret == -1) continue;
			cout << "M[" << i << "] = " << ret << ";" << endl;
		}
	}
}


int32_t main() {
	M[1] = 0;
	M[3] = 1;
	M[7] = 0;
	M[15] = 0;
	M[33] = 1;
	M[35] = 0;
	M[39] = 1;
	M[67] = 0;
	M[71] = 1;
	M[97] = 0;
	M[98] = 0;
	M[99] = 0;
	M[102] = 1;
	M[135] = 1;
	M[195] = 1;
	M[225] = 1;
	M[226] = 1;
	M[228] = 1;
	M[1057] = 0;
	M[1059] = 1;
	M[1121] = 1;
	M[1122] = 1;
	M[2115] = 1;
	M[2145] = 1;
	M[2146] = 1;
	M[3105] = 1;
	M[3138] = 1;
	M[33825] = 0;
	// gen();
	// return 0;

	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	cin >> t;

	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

详细

Test #1:

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

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: 3468kb

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