QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#847798#7725. Just Sum Two NumbersliyujiaAC ✓29ms24112kbC++171.7kb2025-01-08 11:29:182025-01-08 11:29:18

Judging History

This is the latest submission verdict.

  • [2025-01-08 11:29:18]
  • Judged
  • Verdict: AC
  • Time: 29ms
  • Memory: 24112kb
  • [2025-01-08 11:29:18]
  • Submitted

answer

#include <bits/stdc++.h> 
#define int long long
using namespace std;
const int N = 1000005, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}, Dx[] = {0, -1, -1, -1, 0, 1, 1, 1}, Dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
int n, m, q[N], cnt[2005], vis[1005][1005], C, fl, f[1005][1005], v2[1005][1005];
char c[1005][1005];
struct Node{ int x, y;} a[N];
void dfs(int x, int y){
	if(vis[x][y]) return ;
	vis[x][y] = 1, a[++C] = {x, y};
	for(int i = 0; i < 4; i++) if(c[x + dx[i]][y + dy[i]] == '#') dfs(x + dx[i], y + dy[i]);
}
void dfs2(int x, int y){
	if(v2[x][y]) return ;
	v2[x][y] = 1;
	for(int i = 0; i < 8; i++) if(f[x + Dx[i]][y + Dy[i]]) dfs2(x + Dx[i], y + Dy[i]);
}
signed main(){
	int ans = -5;
	mt19937 rnd(114514);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> c[i][j];
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(c[i][j] == '#' && !vis[i][j]){
		C = 0; int fl = 0; dfs(i, j);
		for(int j = 1; j <= 50; j++){
			int t1 = rnd() % C + 1, t2 = rnd() % C + 1;
			int x1 = a[t1].x, x2 = a[t2].x, y1 = a[t1].y, y2 = a[t2].y;
			double dis = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
			for(int i = 1; i <= C; i++){
				double op = abs((a[i].x - x1) * (y2 - y1) - (a[i].y - y1) * (x2 - x1));
				double ip = (a[i].x - x1) * (x2 - x1) + (a[i].y - y1) * (y2 - y1);
				if(op / dis <= 1.42 && ip >= 0 && ip <= dis * dis) f[a[i].x][a[i].y] = 1;
			}
			int cnt = 0;
			for(int i = 1; i <= C; i++) if(f[a[i].x][a[i].y] && !v2[a[i].x][a[i].y]) dfs2(a[i].x, a[i].y), cnt++;
			for(int i = 1; i <= C; i++) f[a[i].x][a[i].y] = v2[a[i].x][a[i].y] = 0;
			if(cnt > 1){ fl = 1; break;}
		}
		if(fl) ans += 5;
		else ans++;
	}
	cout << ans;
	return 0;
}

詳細信息

Test #1:

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

input:

100 354
.......................................................................................................................................................................................................................................................................................................

output:

17

result:

ok 1 number(s): "17"

Test #2:

score: 0
Accepted
time: 5ms
memory: 11012kb

input:

135 269
.............................................................................................................................................................................................................................................................................
.........................

output:

14

result:

ok 1 number(s): "14"

Test #3:

score: 0
Accepted
time: 7ms
memory: 12376kb

input:

294 451
.......................................................................................................................................................................................................................................................................................................

output:

18

result:

ok 1 number(s): "18"

Test #4:

score: 0
Accepted
time: 4ms
memory: 12380kb

input:

234 701
.......................................................................................................................................................................................................................................................................................................

output:

32

result:

ok 1 number(s): "32"

Test #5:

score: 0
Accepted
time: 15ms
memory: 18540kb

input:

888 585
.......................................................................................................................................................................................................................................................................................................

output:

49

result:

ok 1 number(s): "49"

Test #6:

score: 0
Accepted
time: 12ms
memory: 18404kb

input:

579 350
.......................................................................................................................................................................................................................................................................................................

output:

26

result:

ok 1 number(s): "26"

Test #7:

score: 0
Accepted
time: 24ms
memory: 24112kb

input:

884 910
.......................................................................................................................................................................................................................................................................................................

output:

59

result:

ok 1 number(s): "59"

Test #8:

score: 0
Accepted
time: 12ms
memory: 17088kb

input:

652 717
.......................................................................................................................................................................................................................................................................................................

output:

51

result:

ok 1 number(s): "51"

Test #9:

score: 0
Accepted
time: 13ms
memory: 15636kb

input:

568 468
.......................................................................................................................................................................................................................................................................................................

output:

29

result:

ok 1 number(s): "29"

Test #10:

score: 0
Accepted
time: 28ms
memory: 22180kb

input:

923 959
.......................................................................................................................................................................................................................................................................................................

output:

61

result:

ok 1 number(s): "61"

Test #11:

score: 0
Accepted
time: 3ms
memory: 13492kb

input:

361 295
.......................................................................................................................................................................................................................................................................................................

output:

21

result:

ok 1 number(s): "21"

Test #12:

score: 0
Accepted
time: 17ms
memory: 18548kb

input:

712 929
.......................................................................................................................................................................................................................................................................................................

output:

50

result:

ok 1 number(s): "50"

Test #13:

score: 0
Accepted
time: 26ms
memory: 19424kb

input:

929 970
.......................................................................................................................................................................................................................................................................................................

output:

64

result:

ok 1 number(s): "64"

Test #14:

score: 0
Accepted
time: 3ms
memory: 11184kb

input:

394 346
.......................................................................................................................................................................................................................................................................................................

output:

24

result:

ok 1 number(s): "24"

Test #15:

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

input:

418 578
.......................................................................................................................................................................................................................................................................................................

output:

28

result:

ok 1 number(s): "28"

Test #16:

score: 0
Accepted
time: 9ms
memory: 16128kb

input:

457 499
.......................................................................................................................................................................................................................................................................................................

output:

27

result:

ok 1 number(s): "27"

Test #17:

score: 0
Accepted
time: 26ms
memory: 20132kb

input:

985 955
.......................................................................................................................................................................................................................................................................................................

output:

63

result:

ok 1 number(s): "63"

Test #18:

score: 0
Accepted
time: 7ms
memory: 10216kb

input:

209 704
.......................................................................................................................................................................................................................................................................................................

output:

30

result:

ok 1 number(s): "30"

Test #19:

score: 0
Accepted
time: 3ms
memory: 20812kb

input:

837 156
............................................................................................................................................................
..........................................................................................................................................

output:

37

result:

ok 1 number(s): "37"

Test #20:

score: 0
Accepted
time: 3ms
memory: 9568kb

input:

198 126
..............................................................................................................................
..............................................................................................................................
.........................................

output:

3

result:

ok 1 number(s): "3"

Test #21:

score: 0
Accepted
time: 24ms
memory: 22268kb

input:

996 684
.......................................................................................................................................................................................................................................................................................................

output:

57

result:

ok 1 number(s): "57"

Test #22:

score: 0
Accepted
time: 23ms
memory: 19840kb

input:

803 985
.......................................................................................................................................................................................................................................................................................................

output:

65

result:

ok 1 number(s): "65"

Test #23:

score: 0
Accepted
time: 26ms
memory: 21472kb

input:

948 820
.......................................................................................................................................................................................................................................................................................................

output:

62

result:

ok 1 number(s): "62"

Test #24:

score: 0
Accepted
time: 4ms
memory: 16196kb

input:

470 242
..................................................................................................................................................................................................................................................
....................................................

output:

19

result:

ok 1 number(s): "19"

Test #25:

score: 0
Accepted
time: 9ms
memory: 21476kb

input:

967 248
........................................................................................................................................................................................................................................................
..............................................

output:

49

result:

ok 1 number(s): "49"

Test #26:

score: 0
Accepted
time: 5ms
memory: 12064kb

input:

323 198
......................................................................................................................................................................................................
................................................................................................

output:

17

result:

ok 1 number(s): "17"

Test #27:

score: 0
Accepted
time: 8ms
memory: 16636kb

input:

623 385
.......................................................................................................................................................................................................................................................................................................

output:

31

result:

ok 1 number(s): "31"

Test #28:

score: 0
Accepted
time: 29ms
memory: 24028kb

input:

955 959
.......................................................................................................................................................................................................................................................................................................

output:

65

result:

ok 1 number(s): "65"

Test #29:

score: 0
Accepted
time: 20ms
memory: 23588kb

input:

987 745
.......................................................................................................................................................................................................................................................................................................

output:

56

result:

ok 1 number(s): "56"

Test #30:

score: 0
Accepted
time: 6ms
memory: 11924kb

input:

328 309
.......................................................................................................................................................................................................................................................................................................

output:

14

result:

ok 1 number(s): "14"

Test #31:

score: 0
Accepted
time: 18ms
memory: 16072kb

input:

574 923
.......................................................................................................................................................................................................................................................................................................

output:

47

result:

ok 1 number(s): "47"

Test #32:

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

input:

180 259
...................................................................................................................................................................................................................................................................
...................................

output:

13

result:

ok 1 number(s): "13"

Test #33:

score: 0
Accepted
time: 8ms
memory: 9928kb

input:

169 947
.......................................................................................................................................................................................................................................................................................................

output:

44

result:

ok 1 number(s): "44"

Test #34:

score: 0
Accepted
time: 6ms
memory: 18640kb

input:

892 244
....................................................................................................................................................................................................................................................
..................................................

output:

36

result:

ok 1 number(s): "36"

Test #35:

score: 0
Accepted
time: 14ms
memory: 22068kb

input:

1000 598
......................................................................................................................................................................................................................................................................................................

output:

57

result:

ok 1 number(s): "57"

Test #36:

score: 0
Accepted
time: 14ms
memory: 19880kb

input:

821 608
.......................................................................................................................................................................................................................................................................................................

output:

47

result:

ok 1 number(s): "47"

Test #37:

score: 0
Accepted
time: 11ms
memory: 12856kb

input:

223 988
.......................................................................................................................................................................................................................................................................................................

output:

51

result:

ok 1 number(s): "51"

Test #38:

score: 0
Accepted
time: 3ms
memory: 8524kb

input:

141 139
...........................................................................................................................................
...........................................................................................................................................
...............

output:

2

result:

ok 1 number(s): "2"

Test #39:

score: 0
Accepted
time: 28ms
memory: 21028kb

input:

921 940
.......................................................................................................................................................................................................................................................................................................

output:

51

result:

ok 1 number(s): "51"

Test #40:

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

input:

317 124
............................................................................................................................
............................................................................................................................
.............................................

output:

14

result:

ok 1 number(s): "14"

Test #41:

score: 0
Accepted
time: 12ms
memory: 17652kb

input:

692 482
.......................................................................................................................................................................................................................................................................................................

output:

38

result:

ok 1 number(s): "38"

Test #42:

score: 0
Accepted
time: 9ms
memory: 14908kb

input:

464 313
.......................................................................................................................................................................................................................................................................................................

output:

25

result:

ok 1 number(s): "25"

Test #43:

score: 0
Accepted
time: 12ms
memory: 18340kb

input:

697 545
.......................................................................................................................................................................................................................................................................................................

output:

35

result:

ok 1 number(s): "35"

Test #44:

score: 0
Accepted
time: 7ms
memory: 12160kb

input:

265 445
.......................................................................................................................................................................................................................................................................................................

output:

19

result:

ok 1 number(s): "19"

Test #45:

score: 0
Accepted
time: 5ms
memory: 20884kb

input:

701 197
.....................................................................................................................................................................................................
.................................................................................................

output:

35

result:

ok 1 number(s): "35"

Test #46:

score: 0
Accepted
time: 14ms
memory: 15180kb

input:

572 761
.......................................................................................................................................................................................................................................................................................................

output:

41

result:

ok 1 number(s): "41"

Test #47:

score: 0
Accepted
time: 5ms
memory: 11520kb

input:

254 236
............................................................................................................................................................................................................................................
..........................................................

output:

9

result:

ok 1 number(s): "9"

Test #48:

score: 0
Accepted
time: 17ms
memory: 19732kb

input:

644 866
.......................................................................................................................................................................................................................................................................................................

output:

46

result:

ok 1 number(s): "46"

Test #49:

score: 0
Accepted
time: 16ms
memory: 19420kb

input:

528 898
.......................................................................................................................................................................................................................................................................................................

output:

44

result:

ok 1 number(s): "44"

Test #50:

score: 0
Accepted
time: 11ms
memory: 20376kb

input:

796 387
.......................................................................................................................................................................................................................................................................................................

output:

34

result:

ok 1 number(s): "34"

Test #51:

score: 0
Accepted
time: 24ms
memory: 19300kb

input:

862 785
.......................................................................................................................................................................................................................................................................................................

output:

51

result:

ok 1 number(s): "51"

Test #52:

score: 0
Accepted
time: 18ms
memory: 18820kb

input:

688 663
.......................................................................................................................................................................................................................................................................................................

output:

46

result:

ok 1 number(s): "46"

Test #53:

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

input:

372 589
.......................................................................................................................................................................................................................................................................................................

output:

25

result:

ok 1 number(s): "25"

Test #54:

score: 0
Accepted
time: 5ms
memory: 8208kb

input:

100 1000
......................................................................................................................................................................................................................................................................................................

output:

94

result:

ok 1 number(s): "94"

Test #55:

score: 0
Accepted
time: 4ms
memory: 19856kb

input:

999 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

94

result:

ok 1 number(s): "94"

Test #56:

score: 0
Accepted
time: 22ms
memory: 18392kb

input:

998 1000
......................................................................................................................................................................................................................................................................................................

output:

134

result:

ok 1 number(s): "134"