QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69179#5112. Where Am I?zhangbojuAC ✓1755ms66076kbC++172.0kb2022-12-24 20:57:342022-12-24 20:57:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-24 20:57:37]
  • 评测
  • 测评结果:AC
  • 用时:1755ms
  • 内存:66076kb
  • [2022-12-24 20:57:34]
  • 提交

answer

//test
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;short f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;return;
}
const int M=998244353;
inline void add(int &x,int y){(x+=y)>=M?x-=M:x;}
inline int Mod(int x){return x>=M?x-M:x;}
inline int ksm(int x,int y){
	int s=1;
	while(y){
		if(y&1)s=1ll*s*x%M;
		x=1ll*x*x%M,y>>=1;
	}
	return s;
}
int t,n,m,ch[150000002][2],cur[102][102],tot,px[102][102],py[102][102],ans[102][102],curnum[102][102],mxnum[102][102],num[150000002],tim,oo,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},D[102][102],dis[102][102];
char s[1002][1002];
inline int ask(int x,int y){
	if(x>=1&&x<=n&&y>=1&&y<=m)return s[x][y]=='X';
	return 0;
}
inline int Extend(int x,int y){
	if(ch[x][y])return ch[x][y];
	return ch[x][y]=++tot;
}
int main(){
	read(m),read(n);
	for(int i=1;i<=n;++i)scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			px[i][j]=i,py[i][j]=j,cur[i][j]=Extend(cur[i][j],ask(px[i][j],py[i][j])),curnum[i][j]=mxnum[i][j]=1;
	memset(ans,-1,sizeof(ans));
	while(oo<n*m){
		for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)++num[cur[i][j]];
		for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(ans[i][j]==-1&&num[cur[i][j]]==1)ans[i][j]=tim,++oo;
		for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)--num[cur[i][j]];
		++tim;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				if(ans[i][j]==-1){
					--curnum[i][j];
					px[i][j]+=dx[D[i][j]],py[i][j]+=dy[D[i][j]];
					if(curnum[i][j]==0){
						D[i][j]=(D[i][j]+1)%4;
						if(D[i][j]==2||D[i][j]==0)++mxnum[i][j];
						curnum[i][j]=mxnum[i][j];
					}
					cur[i][j]=Extend(cur[i][j],ask(px[i][j],py[i][j]));
				}
	}
	int sum=0,mx=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			sum+=ans[i][j],mx=max(mx,ans[i][j]);
	printf("%.3lf\n%d\n",1.0*sum/n/m,mx);
	for(int i=n;i;--i)
		for(int j=1;j<=m;++j)
			if(ans[i][j]==mx)
				printf("(%d,%d) ",j,n-i+1);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
X

output:

0.000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 451ms
memory: 66076kb

input:

100 100
..X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X..
....................................................................................................
X............................................................................................

output:

4757.947
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 1755ms
memory: 4536kb

input:

100 100
X...................................................................................................
....................................................................................................
.............................................................................................

output:

19735.320
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 1731ms
memory: 4504kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19865.670
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: 0
Accepted
time: 1436ms
memory: 50784kb

input:

100 100
X...................................................................................................
.X..................................................................................................
..X..........................................................................................

output:

11855.639
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

score: 0
Accepted
time: 1441ms
memory: 50464kb

input:

100 100
...................................................................................................X
..................................................................................................X.
.............................................................................................

output:

11854.610
39104
(1,99) (2,100) 

result:

ok correct!

Test #13:

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

input:

20 73
...........X........
.X..................
....................
X.....X........X....
......X........X....
....................
....................
.X..................
....................
...........X........
.X..................
X...................
.......X........X...
.X....X........X....
...

output:

50.098
80
(7,6) (16,6) (20,12) (7,15) (16,15) (7,24) (16,24) (7,33) (16,33) (7,42) (16,42) (19,46) (12,47) (20,47) (7,51) (16,51) (12,56) (19,56) (7,60) (16,60) (20,65) (20,67) (7,69) (16,69) 

result:

ok correct!

Test #14:

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

input:

65 57
..............X..................................................
.................................................................
.........................................................X.......
........X.........X..............................................
..X.....X........................

output:

100.711
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

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

input:

56 59
........................................................
........................................................
........................................................
........................................................
........................................................
X...........

output:

494.498
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

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

input:

46 83
..........X...X.................X.............
..............................X...............
...X..........................................
.....................................X........
...X...........................X...X..........
.X............................................
...............

output:

122.545
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

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

input:

51 57
........................X..........................
............................X......................
....................X.............X................
..................................................X
...................................................
.........................X...........

output:

103.487
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

score: 0
Accepted
time: 36ms
memory: 9360kb

input:

64 91
................................................................
................................................................
................................................................
................................................................
.....................................

output:

480.573
1215
(64,71) (63,91) 

result:

ok correct!

Test #19:

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

input:

75 40
.............................................X............X................
....................X..............................X.......................
...........................................X...........X...........X.......
...........................................X.....X......X............

output:

79.149
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

score: 0
Accepted
time: 30ms
memory: 10820kb

input:

97 54
.............X...................................................................................
..................................X..............................................................
....X............................................................................................
...

output:

383.808
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

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

input:

89 49
...............X...........X.............................................................
.............................................................X..X...........X............
.................................X.......................................................
...........................

output:

161.070
520
(89,1) (2,41) 

result:

ok correct!

Test #22:

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

input:

80 55
.............................................................X..................
................................................................................
.................................................................XX.............
..............................................X.......

output:

176.083
611
(80,2) (79,37) 

result:

ok correct!

Test #23:

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

input:

61 59
...........X.................................................
.............................................................
.......................................................X.....
.............................................................
...............................X.................

output:

291.706
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

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

input:

48 74
....X.X.X.......................................
...............X.....X...X......................
..........................................X.....
................................................
................................................
.......X........................................
...

output:

152.162
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

score: 0
Accepted
time: 32ms
memory: 7744kb

input:

100 96
.................................................................X..................................
.............................X......................................................................
..............................................................................................

output:

212.396
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

score: 0
Accepted
time: 54ms
memory: 6376kb

input:

94 84
..............................................................................................
..............................................................................................
..............................................................................................
............

output:

357.121
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

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

input:

86 80
...........................................................X..........X...............
......................................................................................
X.....................................................................................
....................................

output:

225.856
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

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

input:

81 57
.X............X..................................................................
.................................................................................
.....................................X.........X.............X...................
...................................................

output:

139.734
647
(24,1) (81,4) 

result:

ok correct!

Test #29:

score: 0
Accepted
time: 69ms
memory: 15276kb

input:

65 85
.................................................................
.................................................................
.................................................................
...................X.............................................
.................................

output:

738.974
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

score: 0
Accepted
time: 152ms
memory: 22744kb

input:

76 98
............................................................................
............................................................................
............................................................................
..................................................................

output:

1550.391
4192
(76,34) (76,96) 

result:

ok correct!

Test #31:

score: 0
Accepted
time: 41ms
memory: 11392kb

input:

62 67
..............................................................
..............................................................
.........................X....................................
...................................................X..........
.............................................

output:

648.650
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

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

input:

50 98
..........................................X.......
.................................X...............X
..................................................
..................................................
.............................................X....
..........................................

output:

207.338
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

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

input:

74 97
....................X.....................................................
..........................................................................
..........................................................................
................................X.......................................

output:

193.030
1078
(74,70) (71,93) 

result:

ok correct!

Test #34:

score: 0
Accepted
time: 118ms
memory: 38332kb

input:

62 77
..............................................................
..............................................................
..............................................................
..............................................................
.............................................

output:

2021.070
4937
(46,73) (8,77) 

result:

ok correct!

Test #35:

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

input:

47 74
...............................................
...............................................
...............................................
.....................X.........................
...............................................
............................................X..
.........

output:

142.154
673
(1,74) (2,74) 

result:

ok correct!

Test #36:

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

input:

47 71
...........X....X..............................
...............................................
...............................................
...........X...................................
.............................................X.
..X...........XX............X..................
.........

output:

102.814
334
(44,4) (47,37) 

result:

ok correct!

Test #37:

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

input:

51 65
.........X..........X..............................
.................................X....X.........X..
................................................X..
...................................................
...................................................
.....................................

output:

81.670
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

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

input:

40 93
.......X................................
........................................
........................................
........................................
.X......................................
..................X.....................
........................................
..........

output:

300.308
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

score: 0
Accepted
time: 56ms
memory: 11536kb

input:

87 99
.......................................................................................
.......................................................................................
.......................................................................................
.................................

output:

474.069
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

score: 0
Accepted
time: 126ms
memory: 32812kb

input:

46 94
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
...............

output:

2555.367
5914
(46,1) (46,2) 

result:

ok correct!

Test #41:

score: 0
Accepted
time: 218ms
memory: 13180kb

input:

93 60
.............................................................................................
.............................................................................................
.............................................................................................
...............

output:

2389.200
11288
(21,60) (22,60) 

result:

ok correct!

Test #42:

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

input:

98 61
.............................................X................................X...................
...................................................................X.............X................
..................................................................................X................

output:

225.089
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

score: 0
Accepted
time: 27ms
memory: 5744kb

input:

94 95
..............................................................................................
.......................................................X......................................
............X................................................X.......................X........
............

output:

213.688
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

score: 0
Accepted
time: 197ms
memory: 41348kb

input:

94 72
..............................................................................................
..............................................................................................
..............................................................................................
............

output:

1330.090
4671
(60,71) (38,72) 

result:

ok correct!

Test #45:

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

input:

46 44
....X...X..............................X...X..
................................X..X......X...
..............X.........X.....................
......................X...........X...........
......................X.X........X.X...X......
.............X..........X.....................
.X.............

output:

67.355
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

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

input:

65 51
.................................................................
.........................X.......................................
........X..............X.........................................
....X...............X............................................
.................................

output:

80.041
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

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

input:

51 82
...................................................
...............X...........X.........X.............
..............................X....................
...................................................
...................................................
.......................X.............

output:

100.466
360
(49,3) (51,62) 

result:

ok correct!

Test #48:

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

input:

87 60
.......................................................................................
........................................................................X..............
.......................................................................................
.................................

output:

302.790
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

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

input:

53 44
...................................X.................
.....................................................
............................X....X...................
...X.................................................
.....................................................
....................X......

output:

150.347
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

score: 0
Accepted
time: 114ms
memory: 18992kb

input:

94 97
..............................................................................................
.......................................X......................X...............................
..............................................................................................
............

output:

690.646
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

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

input:

70 68
......................................................................
.....................X...........................X....................
........X...........................X...........................X.....
......................................................................
.............

output:

356.975
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

score: 0
Accepted
time: 194ms
memory: 46196kb

input:

100 91
....................................................................................................
....................................................................................................
..............................................................................................

output:

1705.102
4664
(100,44) (100,90) 

result:

ok correct!

Test #53:

score: 0
Accepted
time: 303ms
memory: 43676kb

input:

88 84
........................................................................................
........................................................................................
........................................................................................
..............................

output:

2976.142
8305
(68,1) (69,1) 

result:

ok correct!

Test #54:

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

input:

48 44
................................................
................................................
..........X...........X.........................
...X............................................
...........................X....................
.........X......................................
...

output:

140.188
466
(8,7) (1,20) 

result:

ok correct!

Test #55:

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

input:

98 60
......................................X.....X.....................................................
......................................X..............................X............................
............X......................................................X...............................

output:

179.279
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

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

input:

58 41
...............................X...............X..........
..X..................X....X...............................
..........................................................
.....................X.............................X......
..............................X.................X............

output:

75.130
228
(2,1) (49,27) 

result:

ok correct!

Test #57:

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

input:

95 48
....X.......X.......................X..............X........................X...........X......
........X...............................X...............................X......................
........................XX...............................X.....................................
.........

output:

115.941
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

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

input:

51 62
...................................................
..............................X.........X..........
................................................X..
.......................X...........................
..............................................X....
.....................................

output:

127.050
432
(7,1) (51,6) 

result:

ok correct!

Test #59:

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

input:

86 98
.......X......X.......................................................................
......................................................................................
......................................................................................
....................................

output:

215.501
732
(66,70) (68,72) 

result:

ok correct!

Test #60:

score: 0
Accepted
time: 45ms
memory: 6568kb

input:

91 94
...........................................................................................
...........................................................................................
...........................................................................................
.....................

output:

309.110
1541
(78,1) (90,8) 

result:

ok correct!

Test #61:

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

input:

74 45
..........................................................................
..........................................................................
....X.............X..........................................X............
.X................X..........................X............X.............

output:

164.878
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

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

input:

54 73
.....X.......X........................................
.............X........................................
...............X......................................
................................X.....................
..............................................X.......
......................

output:

106.013
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

score: 0
Accepted
time: 27ms
memory: 12200kb

input:

91 56
...........................................................................................
..............................X.............................X..............................
.....................................................................X.....................
.....................

output:

423.715
1455
(63,19) (24,20) 

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.000
1
(1,1) (1,2) 

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.250
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.750
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.750
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.500
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.750
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.250
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.000
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.500
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.750
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.000
5
(1,3) (1,4) 

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.750
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.750
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.500
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.750
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.250
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.500
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.250
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.500
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.500
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.750
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.750
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.500
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.500
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.750
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.500
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.250
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.250
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.500
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.000
3
(1,1) (3,1) 

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.000
3
(1,1) (2,1) 

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.000
3
(1,1) (2,1) 

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.333
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.000
3
(2,1) (3,1) 

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.750
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.250
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5.000
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.250
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.500
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.250
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.750
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.000
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.500
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.250
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.250
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.250
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.500
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

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

input:

100 1
X...................................................................................................

output:

13274.590
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

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

input:

100 1
...................................................................................................X

output:

13076.630
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

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

input:

100 1
..................................................X.................................................

output:

3356.010
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.500
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

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

input:

100 1
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.

output:

3554.940
9950
(49,1) (51,1) 

result:

ok correct!

Test #129:

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

input:

100 2
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X

output:

3451.070
9751
(49,1) (51,1) 

result:

ok correct!

Test #130:

score: 0
Accepted
time: 33ms
memory: 6300kb

input:

1 100
X
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

12977.650
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

score: 0
Accepted
time: 33ms
memory: 4412kb

input:

1 100
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X

output:

13175.610
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

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

input:

1 100
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
X
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

3306.030
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

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

input:

1 100
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

output:

3406.500
9850
(1,50) (1,51) 

result:

ok correct!

Test #134:

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

input:

1 100
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.
X
.

output:

3503.020
9850
(1,50) (1,52) 

result:

ok correct!

Test #135:

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

input:

2 100
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
...

output:

3401.110
9654
(2,49) (2,51) 

result:

ok correct!

Test #136:

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

input:

10 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

output:

58.080
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

score: 0
Accepted
time: 1658ms
memory: 9524kb

input:

100 100
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
....................................................................................................
.............................................................................................

output:

13878.927
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

score: 0
Accepted
time: 1623ms
memory: 10196kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

14059.272
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

score: 0
Accepted
time: 1455ms
memory: 9140kb

input:

100 100
X...................................................................................................
X...................................................................................................
X............................................................................................

output:

14132.282
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

score: 0
Accepted
time: 1428ms
memory: 9844kb

input:

100 100
...................................................................................................X
...................................................................................................X
.............................................................................................

output:

13951.433
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

score: 0
Accepted
time: 1713ms
memory: 4564kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19733.340
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

score: 0
Accepted
time: 1728ms
memory: 4536kb

input:

100 100
...................................................................................................X
....................................................................................................
.............................................................................................

output:

19601.010
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

score: 0
Accepted
time: 446ms
memory: 6184kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

5001.490
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

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

input:

20 20
.XX......XX.....XXXX
..X.....X..X....X...
.....X..............
X..XX.X..XX......XX.
X..........X........
...X..X............X
.X...X..........XXXX
.X...XX..XX....X....
X.X.XX...X.......X.X
XXXXX....X........X.
.X.XX.X..XX...X.X...
X.......X..XXX.....X
.X..X..X.X......X...
.........X....X...X.
...

output:

12.812
31
(13,5) (15,18) 

result:

ok correct!

Test #145:

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

input:

50 50
..................................................
..................X...............X...............
..................................................
....X...X........................X........X..X....
.................X................................
..........................................

output:

60.831
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

score: 0
Accepted
time: 39ms
memory: 7988kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

227.535
1062
(96,95) (55,100) 

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed