QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#847903#7725. Just Sum Two NumbersCarroT1212AC ✓9ms24576kbC++141.8kb2025-01-08 13:00:172025-01-08 13:00:18

Judging History

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

  • [2025-01-08 13:00:18]
  • 评测
  • 测评结果:AC
  • 用时:9ms
  • 内存:24576kb
  • [2025-01-08 13:00:17]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=1007,xx[8]={-1,0,1,0,-1,-1,1,1},yy[8]={0,-1,0,1,-1,1,1,-1};
const ld B=2;
ll n,m,vis[N][N],has[N][N],can[N][N],ans;
char str[N][N];
vector<pll> v;
void dfs(ll x,ll y) {
	vis[x][y]=1,v.pb({x,y});
	for (ll i=0;i<8;i++) {
		ll nx=x+xx[i],ny=y+yy[i];
		if (str[nx][ny]=='#'&&!vis[nx][ny]) dfs(nx,ny);
	}
}
void dfs1(ll x,ll y) {
	has[x][y]=1;
	for (ll i=0;i<8;i++) {
		ll nx=x+xx[i],ny=y+yy[i];
		if (can[nx][ny]&&!has[nx][ny]) dfs1(nx,ny);
	}
}
pll operator - (pll x,pll y) { return {x.fi-y.fi,x.se-y.se}; }
ll operator * (pll x,pll y) { return x.fi*y.se-x.se*y.fi; }
ll operator & (pll x,pll y) { return x.fi*y.fi+x.se*y.se; }
ld len(pll x) { return sqrt((ld)(x.fi*x.fi+x.se*x.se)); }
ld dis(pll a,pll b,pll c) { return (ld)abs((c-a)*(b-a))/len(b-a); }
mt19937_64 dnr(9);
ll rnd(ll l,ll r) { return dnr()%(r-l+1)+l; }
void solve(ll sx,ll sy) {
	v.clear(),dfs(sx,sy);
	sort(v.begin(),v.end());
	ll mx=0;
	for (ll o=0;o<30&&mx<=1;o++) {
		pll s=v[rnd(0,(ll)v.size()-1)],t;
		while (t=v[rnd(0,(ll)v.size()-1)],s==t);
		for (pll i:v) {
			ll d=(t-s)&(i-s);
			has[i.fi][i.se]=0,can[i.fi][i.se]=dis(s,t,i)<=B&&0<=d&&d<=len(t-s)*len(t-s);
		}
		ll sum=0;
		for (pll i:v) if (can[i.fi][i.se]&&!has[i.fi][i.se]) dfs1(i.fi,i.se),sum++;
		mx=max(mx,sum);
	}
	ans+=mx<=1?1:5;
}
void mian() {
	scanf("%lld%lld",&n,&m);
	for (ll i=1;i<=n;i++) scanf("%s",str[i]+1);
	for (ll i=1;i<=n;i++) for (ll j=1;j<=m;j++) if (str[i][j]=='#'&&!vis[i][j]) solve(i,j);
	cout<<ans-5;
}
bool ORY; int main() {
	// while (1)
	// int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 8252kb

input:

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

output:

17

result:

ok 1 number(s): "17"

Test #2:

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

input:

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

output:

14

result:

ok 1 number(s): "14"

Test #3:

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

input:

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

output:

18

result:

ok 1 number(s): "18"

Test #4:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #5:

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

input:

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

output:

49

result:

ok 1 number(s): "49"

Test #6:

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

input:

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

output:

26

result:

ok 1 number(s): "26"

Test #7:

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

input:

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

output:

59

result:

ok 1 number(s): "59"

Test #8:

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

input:

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

output:

51

result:

ok 1 number(s): "51"

Test #9:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #10:

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

input:

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

output:

61

result:

ok 1 number(s): "61"

Test #11:

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

input:

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

output:

21

result:

ok 1 number(s): "21"

Test #12:

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

input:

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

output:

50

result:

ok 1 number(s): "50"

Test #13:

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

input:

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

output:

64

result:

ok 1 number(s): "64"

Test #14:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #15:

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

input:

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

output:

28

result:

ok 1 number(s): "28"

Test #16:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #17:

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

input:

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

output:

63

result:

ok 1 number(s): "63"

Test #18:

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

input:

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

output:

30

result:

ok 1 number(s): "30"

Test #19:

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

input:

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

output:

37

result:

ok 1 number(s): "37"

Test #20:

score: 0
Accepted
time: 2ms
memory: 9224kb

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #21:

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

input:

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

output:

57

result:

ok 1 number(s): "57"

Test #22:

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

input:

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

output:

65

result:

ok 1 number(s): "65"

Test #23:

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

input:

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

output:

62

result:

ok 1 number(s): "62"

Test #24:

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Test #25:

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

input:

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

output:

49

result:

ok 1 number(s): "49"

Test #26:

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

input:

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

output:

17

result:

ok 1 number(s): "17"

Test #27:

score: 0
Accepted
time: 2ms
memory: 18708kb

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #28:

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

input:

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

output:

65

result:

ok 1 number(s): "65"

Test #29:

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

input:

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

output:

56

result:

ok 1 number(s): "56"

Test #30:

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

input:

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

output:

14

result:

ok 1 number(s): "14"

Test #31:

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

input:

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

output:

47

result:

ok 1 number(s): "47"

Test #32:

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

input:

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

output:

13

result:

ok 1 number(s): "13"

Test #33:

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

input:

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

output:

44

result:

ok 1 number(s): "44"

Test #34:

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

input:

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

output:

36

result:

ok 1 number(s): "36"

Test #35:

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

input:

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

output:

57

result:

ok 1 number(s): "57"

Test #36:

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

input:

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

output:

47

result:

ok 1 number(s): "47"

Test #37:

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

input:

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

output:

51

result:

ok 1 number(s): "51"

Test #38:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #39:

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

input:

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

output:

51

result:

ok 1 number(s): "51"

Test #40:

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

input:

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

output:

14

result:

ok 1 number(s): "14"

Test #41:

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

input:

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

output:

38

result:

ok 1 number(s): "38"

Test #42:

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

input:

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

output:

25

result:

ok 1 number(s): "25"

Test #43:

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

input:

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

output:

35

result:

ok 1 number(s): "35"

Test #44:

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Test #45:

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

input:

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

output:

35

result:

ok 1 number(s): "35"

Test #46:

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

input:

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

output:

41

result:

ok 1 number(s): "41"

Test #47:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #48:

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

input:

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

output:

46

result:

ok 1 number(s): "46"

Test #49:

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

input:

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

output:

44

result:

ok 1 number(s): "44"

Test #50:

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

input:

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

output:

34

result:

ok 1 number(s): "34"

Test #51:

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

input:

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

output:

51

result:

ok 1 number(s): "51"

Test #52:

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

input:

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

output:

46

result:

ok 1 number(s): "46"

Test #53:

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

input:

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

output:

25

result:

ok 1 number(s): "25"

Test #54:

score: 0
Accepted
time: 2ms
memory: 8220kb

input:

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

output:

94

result:

ok 1 number(s): "94"

Test #55:

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

input:

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

output:

94

result:

ok 1 number(s): "94"

Test #56:

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

input:

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

output:

134

result:

ok 1 number(s): "134"