QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207367#5818. Macaronabcpony100 ✓1116ms67984kbC++201.8kb2023-10-08 14:47:112023-10-08 14:47:11

Judging History

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

  • [2023-10-08 14:47:11]
  • 评测
  • 测评结果:100
  • 用时:1116ms
  • 内存:67984kb
  • [2023-10-08 14:47:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, a, b) for (int i = a; i <= (b); i++)
#define drep(i, a, b) for (int i = a; i >= (b); i--)
// abc <= ((a+b+c)/3)^3  所以 (N-2r)^2 * 4r <= N^3 / 27
const int maxn = 1005, dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int vis[maxn][maxn], a[maxn][maxn], n, m, rr, r, sx, sy, k, X[maxn * 2], Y[maxn * 2], VIS[maxn][maxn], num;
int cal(int x1, int y1, int x2, int y2) {
	return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
bool chk(int x, int y) {
	if (!(x - r >= 0 && x + r <= n + 1 && y - r >= 0 && y + r <= m + 1))
		return 0;
	rep(i, 1, num) if (a[X[i]][Y[i]]) return 0;
	return 1;
}
void dfs(int x, int y) {
	rep(i, 0, 3) {
		int xx = x + dx[i], yy = y + dy[i];
		rep(j, 1, num) X[j] += dx[i], Y[j] += dy[i];
		if (chk(xx, yy) && !vis[xx][yy]) {
			vis[xx][yy] = 1;
			dfs(xx, yy);
		}
		rep(j, 1, num) X[j] -= dx[i], Y[j] -= dy[i];
	}
}
signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> rr >> sx >> sy >> k;
	r = ceil(sqrt(rr)) + 1e-14;
	rep(i, 1, n) {
		int lm = maxn, rm = -1;
		rep(j, 1, m) {
			if (cal(i, j, sx, sy) < rr) {
				lm = min(lm, j);
				rm = max(rm, j);
			}
		}
		if (lm < maxn)
			X[++num] = i, Y[num] = lm, VIS[i][lm] = 1;
		if (~rm && rm != lm)
			X[++num] = i, Y[num] = rm, VIS[i][rm] = 1;
	}
	rep(j, 1, m) {
		int lm = maxn, rm = -1;
		rep(i, 1, n) {
			if (cal(i, j, sx, sy) < rr) {
				lm = min(lm, i);
				rm = max(rm, i);
			}
		}
		if (lm < maxn && !VIS[lm][j])
			X[++num] = lm, Y[num] = j;
		if (~rm && rm != lm && !VIS[rm][j])
			X[++num] = rm, Y[num] = j;
	}
	rep(i, 1, k) {
		int x, y;
		cin >> x >> y;
		a[x][y] = 1;
	}
	vis[sx][sy] = 1;
	dfs(sx, sy);
	int cnt = 0;
	rep(i, 1, n) {
		rep(j, 1, m) {
			cnt += vis[i][j];
		}
	}
	cout << cnt;

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 1ms
memory: 7544kb

input:

11 11
5
9 7
4
1 10
1 11
8 3
8 4

output:

37

result:

ok single line: '37'

Test #2:

score: 10
Accepted
time: 619ms
memory: 55836kb

input:

999 999
3000
340 211
25
230 432
513 610
514 610
360 56
360 55
474 319
474 318
687 476
687 477
204 142
205 142
206 142
207 142
244 511
243 511
242 511
241 511
32 652
32 653
32 654
32 655
197 976
539 579
540 579
540 578

output:

724629

result:

ok single line: '724629'

Test #3:

score: 10
Accepted
time: 794ms
memory: 67096kb

input:

1000 1000
5000
748 173
24
944 654
943 654
944 653
942 654
941 654
941 655
942 655
940 655
939 655
938 655
939 656
938 656
635 128
636 128
634 128
635 127
637 128
633 128
632 128
633 127
631 128
630 128
629 128
628 128

output:

716645

result:

ok single line: '716645'

Test #4:

score: 10
Accepted
time: 326ms
memory: 20556kb

input:

1000 1000
10000
668 126
30
9 589
39 505
165 527
185 25
211 383
231 699
235 849
291 839
317 955
319 627
355 79
355 117
365 521
447 253
473 721
515 161
517 157
587 465
627 849
641 515
729 893
775 81
783 583
813 1
839 699
869 215
931 365
937 975
941 47
965 249

output:

192418

result:

ok single line: '192418'

Test #5:

score: 10
Accepted
time: 1ms
memory: 7780kb

input:

50 50
30
36 40
11
50 41
29 16
31 23
48 9
27 22
8 33
9 33
1 40
3 39
27 21
29 30

output:

1200

result:

ok single line: '1200'

Test #6:

score: 10
Accepted
time: 0ms
memory: 7792kb

input:

100 100
300
69 24
17
32 34
33 34
31 34
40 55
32 10
98 77
97 77
96 77
81 71
19 69
87 66
88 66
88 67
100 38
100 37
19 89
13 48

output:

1730

result:

ok single line: '1730'

Test #7:

score: 10
Accepted
time: 712ms
memory: 51028kb

input:

1000 1000
5000
845 228
41
13 132
12 132
13 133
13 131
11 132
12 133
14 131
11 131
908 888
907 888
401 736
350 495
350 494
349 494
348 494
349 493
348 495
350 493
347 495
348 496
351 493
349 496
348 497
351 492
351 491
859 937
295 732
295 733
151 720
152 720
151 721
152 721
151 722
37 291
675 123
676...

output:

646861

result:

ok single line: '646861'

Test #8:

score: 10
Accepted
time: 1116ms
memory: 67984kb

input:

1000 1000
10000
845 168
7949
901 901
901 902
901 903
901 904
901 905
901 906
901 909
901 911
901 912
901 913
901 914
901 915
901 916
901 917
901 918
901 919
901 920
901 921
901 923
901 924
901 925
901 926
901 927
901 928
901 930
901 935
901 936
901 938
901 939
901 940
901 942
901 943
901 945
901 946...

output:

635255

result:

ok single line: '635255'

Test #9:

score: 10
Accepted
time: 53ms
memory: 40000kb

input:

1000 1000
1
19 587
249999
1 1
1 3
1 5
1 7
1 9
1 11
1 13
1 15
1 17
1 19
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
1 37
1 39
1 41
1 43
1 45
1 47
1 49
1 51
1 53
1 55
1 57
1 59
1 61
1 63
1 65
1 67
1 69
1 71
1 73
1 75
1 77
1 79
1 81
1 83
1 85
1 87
1 89
1 91
1 93
1 95
1 97
1 99
1 101
1 103
1 105
1 107
1 109...

output:

750001

result:

ok single line: '750001'

Test #10:

score: 10
Accepted
time: 772ms
memory: 18924kb

input:

1000 1000
111012
587 619
0

output:

111556

result:

ok single line: '111556'

Extra Test:

score: 0
Extra Test Passed