QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#318775#7733. Cool, It’s Yesterday Four Times Moreamirali_asgari#WA 2ms5736kbC++202.6kb2024-01-31 20:14:012024-01-31 20:14:01

Judging History

你现在查看的是最新测评结果

  • [2024-01-31 20:14:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5736kb
  • [2024-01-31 20:14:01]
  • 提交

answer

// In the name of Allah

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

typedef 	long long int			ll;
typedef 	long double				ld;
typedef 	pair<int, int>			pii;
typedef 	pair<ll, ll>			pll;
typedef 	complex<ld>				cld;

#define 	all(x)					(x).begin(),(x).end()
#define 	len(x)					((ll) (x).size())
#define 	F						first
#define 	S						second
#define		X						real()
#define		Y						imag()
#define 	pb						push_back
#define 	sep						' '
#define 	endl					'\n'
#define 	Mp						make_pair
#define 	kill(x)					cout << x << '\n', exit(0)
#define 	set_dec(x)				cout << fixed << setprecision(x);
#define 	file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);

int n, m;
const int maxn = 2e5 + 4;
vector<char> s[maxn]; int M[maxn];
int mark[maxn], col[maxn], c = 0;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
vector<pii> A[maxn];

int GI(int i, int j) {
	return (i * m + j);
}

pii Gp(int v) {
	return Mp(v / m, v % m);
}

void dfs(int v) {
	auto f = Gp(v);
	int x = f.F, y = f.S;
	mark[v] = 1; col[v] = c; A[c].pb(Mp(x, y));
	for (int T = 0; T < 4; T++) {
		int x1 = x + dx[T], y1 = y + dy[T];
		if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && s[x1][y1] == '.') {
			int u = GI(x1, y1);
			if (!mark[u]) dfs(u);
		}
	}
}

bool ok(int i, int j) {
	auto f = A[i][0];
	for (auto g : A[j]) {
		pii d = Mp(g.F - f.F, g.S - f.S);
		bool flag = 1;
		for (auto r : A[i]) {
			int x1 = r.F + d.F, y1 = r.S + d.S;
			if (!(x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && col[GI(x1, y1)] == j)) {
				flag = 0;
				break;
			}
		}
		if (flag) return 1;
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			s[i].clear(); s[i].resize(m);
			for (int j = 0; j < m; j++) cin >> s[i][j];
		}
		
		fill(mark, mark + (n * m), 0); c = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (s[i][j] != '.') continue;
				int v = GI(i, j);
				if (!mark[v]) {
					A[c].clear();
					dfs(v); c++;
				}
			}
		}
		
		fill(M, M + c, 1);
		for (int i = 0; i < c; i++) {
			for (int j = i + 1; j < c; j++) {
				if (len(A[i]) == len(A[j])) {
					if (ok(i, j)) {
						M[i] = 0; M[j] = 0;
					}
				}
				else if (len(A[i]) > len(A[j])) {
					if (ok(j, i)) M[j] = 0;
				}
				else {
					if (ok(i, j)) M[i] = 0;
				}
			}
		}
		
		int res = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (s[i][j] != '.') continue;
				int v = GI(i, j);
				if (M[col[v]]) res++;
			}
		}
		cout << res << endl;
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5736kb

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

3
1
0
0

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 5688kb

input:

200
2 4
OOO.
OO..
2 3
OOO
.O.
3 3
O.O
OOO
OO.
4 1
.
.
O
O
1 2
.O
1 1
.
2 5
.OO..
.O.O.
2 1
O
O
1 1
O
1 3
.OO
5 1
O
O
.
O
.
5 2
O.
..
O.
.O
..
5 3
...
...
.OO
..O
OOO
3 5
..O.O
.O.O.
.OO.O
5 2
.O
OO
O.
O.
..
2 1
O
O
3 5
.O.OO
O...O
..OO.
1 5
.....
5 1
O
.
O
.
.
5 3
OOO
OO.
.OO
OO.
O.O
2 1
O
.
5 2
O.
...

output:

3
0
0
2
1
1
3
0
0
1
0
7
9
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
4
5
2
3
7
3
0
6
2
2
2
0
4
6
6
3
3
2
3
3
2
1
0
3
3
4
4
2
2
0
7
6
4
8
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
6
1
6
2
2
3
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
6
2
5
1
3
3
4
0
2
11
2
2
4
0
4
0
6
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
1...

result:

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