QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#512328#9170. Cycle Gameucup-team052#WA 1ms5936kbC++231.5kb2024-08-10 14:09:252024-08-10 14:09:27

Judging History

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

  • [2024-08-10 14:09:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5936kb
  • [2024-08-10 14:09:25]
  • 提交

answer

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

typedef pair <int, int> pii;

const int N = 3e5 + 5;
const int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};

priority_queue <pii> Q;
int dis[N], vis[N], w[N];
int n, m, k;

inline int s(int x, int y) {
	return (x - 1) * m + y;
}

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n * m; i++) w[i] = k;
	for (int i = 1; i <= k; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		w[s(x, y)] = i - 1;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int ok = 0;
			for (int d = 0; d < 8; d++) {
				int x = i + dx[d], y = j + dy[d];
				if (x < 1 || y < 1 || x > n || y > m) {
					ok = 1;
					break;
				}
			}
			if (ok) {
				dis[s(i, j)] = w[s(i, j)];
				Q.push(make_pair(dis[s(i, j)], s(i, j)));
			}
		}
	}
	while (!Q.empty()) {
		int u = Q.top().second; Q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		int x = (u - 1) / m + 1;
		int y = (u - 1) % m + 1;
		for (int d = 0; d < 8; d++) {
			int xx = x + dx[d];
			int yy = y + dy[d];
			if (xx >= 1 && yy >= 1 && xx <= n && yy <= m) {
				int v = s(xx, yy);
				if (dis[v] < min(dis[u], w[v])) {
					dis[v] = min(dis[u], w[v]);
					Q.push(make_pair(dis[v], v));
				}
			}
		}
	}
	int ans = k;
	for (int i = 1; i <= n * m; i++) {
		if (dis[i] < w[i]) {
			ans = min(ans, dis[i]);
		}
	}
	for (int i = 1; i <= ans; i++) printf("1");
	for (int i = ans + 1; i <= k; i++) printf("0");
	printf("\n");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3820kb

input:

4 3 7
2 1
2 2
2 3
3 1
3 2
4 1
4 2

output:

1111111

result:

ok "1111111"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5864kb

input:

3 3 8
1 1
1 2
1 3
2 3
3 3
3 2
3 1
2 1

output:

11111110

result:

ok "11111110"

Test #3:

score: 0
Accepted
time: 0ms
memory: 5804kb

input:

10 10 7
9 1
6 6
3 8
8 7
5 10
1 7
1 2

output:

1111111

result:

ok "1111111"

Test #4:

score: 0
Accepted
time: 0ms
memory: 5856kb

input:

9 10 50
1 9
1 6
2 3
3 1
7 4
9 4
1 3
2 5
9 2
7 9
5 6
8 10
9 5
5 5
4 10
9 7
5 9
3 2
4 5
1 1
4 7
3 6
2 8
4 3
8 6
5 10
4 8
5 4
7 2
9 6
4 2
7 8
5 2
3 5
9 1
6 1
1 5
9 9
5 8
6 3
8 8
8 4
7 7
7 1
3 7
2 2
3 10
6 9
8 3
7 6

output:

11111111111111111111111111111111111111111111111111

result:

ok "11111111111111111111111111111111111111111111111111"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

3 5 11
1 5
2 4
1 2
1 3
3 3
3 1
3 4
2 3
1 4
2 1
2 5

output:

11111111111

result:

ok "11111111111"

Test #6:

score: 0
Accepted
time: 1ms
memory: 5852kb

input:

7 9 12
7 3
2 3
6 2
2 2
4 2
2 8
5 7
4 4
6 8
2 7
7 2
1 9

output:

111111111111

result:

ok "111111111111"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

1 4 1
1 2

output:

1

result:

ok "1"

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 5936kb

input:

9 8 67
5 5
8 3
9 5
7 4
5 1
9 3
4 2
2 5
1 7
7 8
7 2
8 5
6 1
8 8
4 4
5 4
1 5
3 4
6 7
2 3
3 7
5 7
2 4
2 7
1 3
7 3
2 8
6 6
6 2
6 3
7 5
9 6
7 6
3 6
1 1
6 4
3 1
5 3
8 7
2 1
4 1
8 4
8 6
3 5
5 8
1 6
1 2
4 6
9 4
1 4
3 3
4 8
8 1
4 7
9 8
3 8
6 5
6 8
3 2
2 2
7 1
9 2
4 3
1 8
4 5
8 2
7 7

output:

1111111111111111111111111111111111111111111110000000000000000000000

result:

wrong answer 1st words differ - expected: '111111111111111111111111111111...1111111110010101101000101101101', found: '111111111111111111111111111111...1111111110000000000000000000000'