QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#665765	#7733. Cool, It’s Yesterday Four Times More	369Pai^#	WA	2ms	8220kb	C++14	2.2kb	2024-10-22 15:11:29	2024-10-22 15:11:48

Judging History

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

[2024-10-22 15:11:48]
评测

测评结果：WA
用时：2ms
内存：8220kb

查看

[2024-10-22 15:11:29]
提交

answer

#include <bits/stdc++.h>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int gx[] = {1, -1, 0, 0}, gy[] = {0, 0, -1, 1};

int T, n, m, C, clr[1005][1005], f[1005];
int idx, id[2005][2005];
char c[1005][1005];
vector<int> vec[10005];

int getid(int x, int y) {
	if (!id[x + n][y + m]) id[x + n][y + m] = ++idx;
	return id[x + n][y + m];
}
int ID(int x, int y) {return (x - 1) * m + y;}
void dfs(int x, int y, int sx, int sy, int cc) {
	// if (x == sx && y == sy) eprintf("(%d, %d)\n", sx, sy);
	// eprintf("%d %d\n", x - sx, y - sy);
	clr[x][y] = cc;
	vec[ID(sx, sy)].push_back(getid(x - sx, y - sy));
	for (int i = 0; i < 4; i++) {
		int xx = x + gx[i], yy = y + gy[i];
		if (xx < 1 || xx > n || yy < 1 || yy > m || c[xx][yy] == 'O' || clr[xx][yy] == cc) continue;
		dfs(xx, yy, sx, sy, cc);
	}
	return;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) scanf(" %c", &c[i][j]), clr[i][j] = 0;
		idx = 0;
		for (int i = -n; i <= n; i++)
			for (int j = -m; j <= m; j++) id[i + n][j + m] = 0;
		C = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (c[i][j] != 'O') {
					vec[getid(i, j)].clear();
					dfs(i, j, i, j, ++C);
				}
		for (int i = 1; i <= n * m; i++) {
			sort(vec[i].begin(), vec[i].end()), f[i] = -1;
			// eprintf("%d: ", i);
			// for (int j : vec[i]) eprintf("%d ", j);
			// eputs("");
		}
		int ans = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				if (c[i][j] == 'O') continue;
				int id = ID(i, j);
				if (f[clr[i][j]] != -1) {ans += f[clr[i][j]]; continue;}
				// eprintf("%d\n", id);
				f[clr[i][j]] = 1;
				for (int k = 1; k <= n * m; k++)
					if (k != id && !vec[k].empty()) {
						int flag = 1;
						for (int l : vec[id]) {
							auto it = lower_bound(vec[k].begin(), vec[k].end(), l);
							if (it == vec[k].end() || *it != l) {flag = 0; break;}
						}
						if (flag) {f[clr[i][j]] = 0; break;}
					}
				ans += f[clr[i][j]];
			}
		printf("%d\n", ans);
	}
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 6192kb

input:

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

output:

result:

ok 4 lines

Test #2:

score: -100

Wrong Answer

time: 2ms

memory: 8220kb

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:

result:

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