QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#798130 | #7725. Just Sum Two Numbers | Kazemaru | AC ✓ | 18ms | 76804kb | C++17 | 1.7kb | 2024-12-04 08:02:17 | 2024-12-04 08:02:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f(i,j,k) for(int i=j;i<=k;++i)
#define g(i,j,k) for(int i=j;i>=k;--i)
int n,m,s,l;
const int N=2e6,M=1111;
const double eps=1e-9;
struct xy{
int x,y;double c,d;
void rd(){cin>>c>>d;x=c*100;y=d*100;}
void cd(int X,int Y){
x-=X;y-=Y;
c=(x||y)?atan2(x,y):9.0;
d=sqrt(x*x+y*y);
x+=X;y+=Y;
}
}p[N];
int ck(xy a,xy b,xy c){return (b.x-a.x)*(c.y-b.y)-(c.x-b.x)*(b.y-a.y);}
vector<xy>TB(vector<xy>a){
if(a.size()<3)return a;
sort(a.begin(),a.end(),[&](xy a,xy b){return a.x==b.x?a.y<b.y:a.x<b.x;});
for(xy&e:a)e.cd(a[0].x,a[0].y);
sort(a.begin(),a.end(),[&](xy a,xy b){return fabs(a.c-b.c)<eps?a.d>b.d:a.c<b.c;});
vector<xy>b;int m=0;
for(xy e:a){
for(;m>1&&ck(b[m-2],b[m-1],e)>=0;--m)b.pop_back();
b.push_back(e);++m;
}
return b;
}
double d(xy a,xy b){return sqrt((b.y-a.y)*(b.y-a.y)+(b.x-a.x)*(b.x-a.x));}
#define vi vector<xy>
int b[M][M],v[M][M],fa[N],x,y;vi q[N];char c[M][M];
int fifa(int x){return x==fa[x]?x:fa[x]=fifa(fa[x]);}
inline void OL(xy a,xy b,xy c){if(abs(ck(a,b,c))<=d(a,b)*2)v[c.x][c.y]=1;}
inline int clc(vi a){
vi b=TB(a);
int n=0,m=b.size(),s=0,x,y;
for(xy e:a)f(i,1,m)OL(b[i-1],b[i%m],e);
for(xy e:a)if(v[e.x][e.y])v[e.x][e.y]=++n,fa[n]=n;
for(xy e:a)if(x=v[e.x][e.y])f(p,-2,2)f(q,-2,2)if(y=v[e.x+p][e.y+q])fa[fifa(x)]=fifa(y);
for(xy e:a)if(x=v[e.x][e.y])s+=fa[x]==x,v[e.x][e.y]=0;
return s<3?1:5;
}
signed main(){
cin>>n>>m;
f(i,1,n)scanf("%s",c[i]+1);
f(i,1,n)f(j,1,m)if(c[i][j]=='#')p[b[i][j]=++s]={i,j},fa[s]=s;
f(i,1,n)f(j,1,m)if(x=b[i][j])f(p,-1,1)f(q,-1,1)if(y=b[i+p][j+q])fa[fifa(x)]=fifa(y);
f(i,1,s)q[fifa(i)].push_back(p[i]);
f(i,1,s)if(q[i].size())l+=clc(q[i]);
cout<<l-5;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 57632kb
input:
100 354 .......................................................................................................................................................................................................................................................................................................
output:
17
result:
ok 1 number(s): "17"
Test #2:
score: 0
Accepted
time: 3ms
memory: 57740kb
input:
135 269 ............................................................................................................................................................................................................................................................................. .........................
output:
14
result:
ok 1 number(s): "14"
Test #3:
score: 0
Accepted
time: 8ms
memory: 62408kb
input:
294 451 .......................................................................................................................................................................................................................................................................................................
output:
18
result:
ok 1 number(s): "18"
Test #4:
score: 0
Accepted
time: 13ms
memory: 62532kb
input:
234 701 .......................................................................................................................................................................................................................................................................................................
output:
32
result:
ok 1 number(s): "32"
Test #5:
score: 0
Accepted
time: 10ms
memory: 70624kb
input:
888 585 .......................................................................................................................................................................................................................................................................................................
output:
49
result:
ok 1 number(s): "49"
Test #6:
score: 0
Accepted
time: 9ms
memory: 68664kb
input:
579 350 .......................................................................................................................................................................................................................................................................................................
output:
26
result:
ok 1 number(s): "26"
Test #7:
score: 0
Accepted
time: 11ms
memory: 70720kb
input:
884 910 .......................................................................................................................................................................................................................................................................................................
output:
59
result:
ok 1 number(s): "59"
Test #8:
score: 0
Accepted
time: 4ms
memory: 68904kb
input:
652 717 .......................................................................................................................................................................................................................................................................................................
output:
51
result:
ok 1 number(s): "51"
Test #9:
score: 0
Accepted
time: 16ms
memory: 69916kb
input:
568 468 .......................................................................................................................................................................................................................................................................................................
output:
29
result:
ok 1 number(s): "29"
Test #10:
score: 0
Accepted
time: 15ms
memory: 73580kb
input:
923 959 .......................................................................................................................................................................................................................................................................................................
output:
61
result:
ok 1 number(s): "61"
Test #11:
score: 0
Accepted
time: 13ms
memory: 66096kb
input:
361 295 .......................................................................................................................................................................................................................................................................................................
output:
21
result:
ok 1 number(s): "21"
Test #12:
score: 0
Accepted
time: 11ms
memory: 68360kb
input:
712 929 .......................................................................................................................................................................................................................................................................................................
output:
50
result:
ok 1 number(s): "50"
Test #13:
score: 0
Accepted
time: 15ms
memory: 66844kb
input:
929 970 .......................................................................................................................................................................................................................................................................................................
output:
64
result:
ok 1 number(s): "64"
Test #14:
score: 0
Accepted
time: 4ms
memory: 64104kb
input:
394 346 .......................................................................................................................................................................................................................................................................................................
output:
24
result:
ok 1 number(s): "24"
Test #15:
score: 0
Accepted
time: 7ms
memory: 58672kb
input:
418 578 .......................................................................................................................................................................................................................................................................................................
output:
28
result:
ok 1 number(s): "28"
Test #16:
score: 0
Accepted
time: 8ms
memory: 58252kb
input:
457 499 .......................................................................................................................................................................................................................................................................................................
output:
27
result:
ok 1 number(s): "27"
Test #17:
score: 0
Accepted
time: 9ms
memory: 74024kb
input:
985 955 .......................................................................................................................................................................................................................................................................................................
output:
63
result:
ok 1 number(s): "63"
Test #18:
score: 0
Accepted
time: 10ms
memory: 64012kb
input:
209 704 .......................................................................................................................................................................................................................................................................................................
output:
30
result:
ok 1 number(s): "30"
Test #19:
score: 0
Accepted
time: 14ms
memory: 69144kb
input:
837 156 ............................................................................................................................................................ ..........................................................................................................................................
output:
37
result:
ok 1 number(s): "37"
Test #20:
score: 0
Accepted
time: 3ms
memory: 60636kb
input:
198 126 .............................................................................................................................. .............................................................................................................................. .........................................
output:
3
result:
ok 1 number(s): "3"
Test #21:
score: 0
Accepted
time: 15ms
memory: 75248kb
input:
996 684 .......................................................................................................................................................................................................................................................................................................
output:
57
result:
ok 1 number(s): "57"
Test #22:
score: 0
Accepted
time: 15ms
memory: 70160kb
input:
803 985 .......................................................................................................................................................................................................................................................................................................
output:
65
result:
ok 1 number(s): "65"
Test #23:
score: 0
Accepted
time: 16ms
memory: 75172kb
input:
948 820 .......................................................................................................................................................................................................................................................................................................
output:
62
result:
ok 1 number(s): "62"
Test #24:
score: 0
Accepted
time: 4ms
memory: 66360kb
input:
470 242 .................................................................................................................................................................................................................................................. ....................................................
output:
19
result:
ok 1 number(s): "19"
Test #25:
score: 0
Accepted
time: 8ms
memory: 76356kb
input:
967 248 ........................................................................................................................................................................................................................................................ ..............................................
output:
49
result:
ok 1 number(s): "49"
Test #26:
score: 0
Accepted
time: 8ms
memory: 64468kb
input:
323 198 ...................................................................................................................................................................................................... ................................................................................................
output:
17
result:
ok 1 number(s): "17"
Test #27:
score: 0
Accepted
time: 12ms
memory: 72284kb
input:
623 385 .......................................................................................................................................................................................................................................................................................................
output:
31
result:
ok 1 number(s): "31"
Test #28:
score: 0
Accepted
time: 16ms
memory: 75332kb
input:
955 959 .......................................................................................................................................................................................................................................................................................................
output:
65
result:
ok 1 number(s): "65"
Test #29:
score: 0
Accepted
time: 7ms
memory: 75072kb
input:
987 745 .......................................................................................................................................................................................................................................................................................................
output:
56
result:
ok 1 number(s): "56"
Test #30:
score: 0
Accepted
time: 6ms
memory: 60700kb
input:
328 309 .......................................................................................................................................................................................................................................................................................................
output:
14
result:
ok 1 number(s): "14"
Test #31:
score: 0
Accepted
time: 10ms
memory: 68752kb
input:
574 923 .......................................................................................................................................................................................................................................................................................................
output:
47
result:
ok 1 number(s): "47"
Test #32:
score: 0
Accepted
time: 8ms
memory: 64064kb
input:
180 259 ................................................................................................................................................................................................................................................................... ...................................
output:
13
result:
ok 1 number(s): "13"
Test #33:
score: 0
Accepted
time: 4ms
memory: 60196kb
input:
169 947 .......................................................................................................................................................................................................................................................................................................
output:
44
result:
ok 1 number(s): "44"
Test #34:
score: 0
Accepted
time: 8ms
memory: 76456kb
input:
892 244 .................................................................................................................................................................................................................................................... ..................................................
output:
36
result:
ok 1 number(s): "36"
Test #35:
score: 0
Accepted
time: 11ms
memory: 72252kb
input:
1000 598 ......................................................................................................................................................................................................................................................................................................
output:
57
result:
ok 1 number(s): "57"
Test #36:
score: 0
Accepted
time: 12ms
memory: 69988kb
input:
821 608 .......................................................................................................................................................................................................................................................................................................
output:
47
result:
ok 1 number(s): "47"
Test #37:
score: 0
Accepted
time: 11ms
memory: 62528kb
input:
223 988 .......................................................................................................................................................................................................................................................................................................
output:
51
result:
ok 1 number(s): "51"
Test #38:
score: 0
Accepted
time: 4ms
memory: 61884kb
input:
141 139 ........................................................................................................................................... ........................................................................................................................................... ...............
output:
2
result:
ok 1 number(s): "2"
Test #39:
score: 0
Accepted
time: 18ms
memory: 74140kb
input:
921 940 .......................................................................................................................................................................................................................................................................................................
output:
51
result:
ok 1 number(s): "51"
Test #40:
score: 0
Accepted
time: 3ms
memory: 63832kb
input:
317 124 ............................................................................................................................ ............................................................................................................................ .............................................
output:
14
result:
ok 1 number(s): "14"
Test #41:
score: 0
Accepted
time: 12ms
memory: 72664kb
input:
692 482 .......................................................................................................................................................................................................................................................................................................
output:
38
result:
ok 1 number(s): "38"
Test #42:
score: 0
Accepted
time: 12ms
memory: 66788kb
input:
464 313 .......................................................................................................................................................................................................................................................................................................
output:
25
result:
ok 1 number(s): "25"
Test #43:
score: 0
Accepted
time: 8ms
memory: 70980kb
input:
697 545 .......................................................................................................................................................................................................................................................................................................
output:
35
result:
ok 1 number(s): "35"
Test #44:
score: 0
Accepted
time: 8ms
memory: 64936kb
input:
265 445 .......................................................................................................................................................................................................................................................................................................
output:
19
result:
ok 1 number(s): "19"
Test #45:
score: 0
Accepted
time: 15ms
memory: 70680kb
input:
701 197 ..................................................................................................................................................................................................... .................................................................................................
output:
35
result:
ok 1 number(s): "35"
Test #46:
score: 0
Accepted
time: 16ms
memory: 66040kb
input:
572 761 .......................................................................................................................................................................................................................................................................................................
output:
41
result:
ok 1 number(s): "41"
Test #47:
score: 0
Accepted
time: 3ms
memory: 62344kb
input:
254 236 ............................................................................................................................................................................................................................................ ..........................................................
output:
9
result:
ok 1 number(s): "9"
Test #48:
score: 0
Accepted
time: 8ms
memory: 65156kb
input:
644 866 .......................................................................................................................................................................................................................................................................................................
output:
46
result:
ok 1 number(s): "46"
Test #49:
score: 0
Accepted
time: 3ms
memory: 65724kb
input:
528 898 .......................................................................................................................................................................................................................................................................................................
output:
44
result:
ok 1 number(s): "44"
Test #50:
score: 0
Accepted
time: 3ms
memory: 68380kb
input:
796 387 .......................................................................................................................................................................................................................................................................................................
output:
34
result:
ok 1 number(s): "34"
Test #51:
score: 0
Accepted
time: 11ms
memory: 73672kb
input:
862 785 .......................................................................................................................................................................................................................................................................................................
output:
51
result:
ok 1 number(s): "51"
Test #52:
score: 0
Accepted
time: 8ms
memory: 70076kb
input:
688 663 .......................................................................................................................................................................................................................................................................................................
output:
46
result:
ok 1 number(s): "46"
Test #53:
score: 0
Accepted
time: 13ms
memory: 62520kb
input:
372 589 .......................................................................................................................................................................................................................................................................................................
output:
25
result:
ok 1 number(s): "25"
Test #54:
score: 0
Accepted
time: 3ms
memory: 61576kb
input:
100 1000 ......................................................................................................................................................................................................................................................................................................
output:
94
result:
ok 1 number(s): "94"
Test #55:
score: 0
Accepted
time: 3ms
memory: 74976kb
input:
999 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
94
result:
ok 1 number(s): "94"
Test #56:
score: 0
Accepted
time: 4ms
memory: 76804kb
input:
998 1000 ......................................................................................................................................................................................................................................................................................................
output:
134
result:
ok 1 number(s): "134"