QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#847798 | #7725. Just Sum Two Numbers | liyujia | AC ✓ | 29ms | 24112kb | C++17 | 1.7kb | 2025-01-08 11:29:18 | 2025-01-08 11:29:18 |
Judging History
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"