QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#88756#5112. Where Am I?ItsJerrAC ✓156ms11344kbC++142.6kb2023-03-17 00:28:032023-03-17 00:28:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-17 00:28:06]
  • 评测
  • 测评结果:AC
  • 用时:156ms
  • 内存:11344kb
  • [2023-03-17 00:28:03]
  • 提交

answer

//source: https://qoj.ac/contest/1050/problem/5112

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

map<pair<int, int>, int> idx;
void prep() {
	int px = 0, py = 0, it = 0;
	idx[make_pair(0, 0)] = 0;
	for (int layer = 1; layer <= 120; ++layer) {
		--px;
		idx[make_pair(px, py)] = ++it;
		for (int i = 1; i < 2 * layer; ++i) idx[make_pair(px, ++py)] = ++it;
		for (int i = 1; i <= 2 * layer; ++i) idx[make_pair(++px, py)] = ++it;
		for (int i = 1; i <= 2 * layer; ++i) idx[make_pair(px, --py)] = ++it;
		for (int i = 1; i <= 2 * layer; ++i) idx[make_pair(--px, py)] = ++it;
	}
}

const int N = 110;
char a[N][N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	if (fopen("icpc_wf_f.inp", "r")) {
		freopen("icpc_wf_f.inp", "r", stdin);
		freopen("icpc_wf_f.out", "w", stdout);
	}

#ifdef LOCAL_MACHINE
	if (fopen("task.inp", "r")) {
		freopen("task.inp", "r", stdin);
		freopen("task.out", "w", stdout);
	}
#endif

	prep();

	int m, n; cin >> n >> m;
	for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];

	vector<pair<int, int>> marked;
	for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (a[i][j] == 'X') marked.emplace_back(i, j);

	vector<tuple<vector<int>, int, int>> v;
	for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) {
			vector<int> cur;
			for (const pair<int, int> &p : marked) {
				int u, v; tie(u, v) = p;
				cur.push_back(idx[make_pair(u - i, v - j)]);
			}
			sort(cur.begin(), cur.end());
			v.emplace_back(cur, i, j);
		}

	sort(v.begin(), v.end());

	int res = 0, mx = 0;
	vector<pair<int, int>> points;

	for (int i = 0; i < m * n; ++i) {
		int cur = 0, ans = 0;
		if (i) {
			for (int t = 0; t < marked.size(); ++t) {
				if (get<0>(v[i])[t] == get<0>(v[i - 1])[t]) ++cur;
				else break;
			}
			ans = max(ans, min(get<0>(v[i])[cur], get<0>(v[i - 1])[cur]));
		}
		cur = 0;
		if (i + 1 < m * n) {
			for (int t = 0; t < marked.size(); ++t) {
				if (get<0>(v[i])[t] == get<0>(v[i + 1])[t]) ++cur;
				else break;
			}
			ans = max(ans, min(get<0>(v[i])[cur], get<0>(v[i + 1])[cur]));
		}
		if (ans > mx) {
			mx = ans;
			points.clear();
		}
		if (ans == mx) points.emplace_back(get<2>(v[i]), m - get<1>(v[i]) + 1);

		res += ans;
	}

	cout << fixed << setprecision(3) << 1.0 * res / (m * n) << "\n";
	cout << mx << "\n";
	sort(points.begin(), points.end(), [&](const pair<int, int> &x, const pair<int, int> &y){
		if (x.second == y.second) return x.first < y.first;
		return x.second < y.second;
	});
	for (const pair<int, int> &i : points) cout << "(" << i.first << "," << i.second << ") ";
}

// ඞඞඞඞඞ you sus

詳細信息

Test #1:

score: 100
Accepted
time: 11ms
memory: 7384kb

input:

1 1
X

output:

0.000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

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

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: 18ms
memory: 7588kb

input:

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

output:

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

result:

ok correct!

Test #10:

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

input:

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

output:

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

result:

ok correct!

Test #11:

score: 0
Accepted
time: 125ms
memory: 11292kb

input:

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

output:

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

result:

ok correct!

Test #12:

score: 0
Accepted
time: 143ms
memory: 11112kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

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: 50ms
memory: 8292kb

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: 16ms
memory: 7452kb

input:

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

output:

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

result:

ok correct!

Test #16:

score: 0
Accepted
time: 49ms
memory: 8328kb

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: 39ms
memory: 8208kb

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: 7992kb

input:

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

output:

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

result:

ok correct!

Test #19:

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

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: 50ms
memory: 8552kb

input:

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

output:

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

result:

ok correct!

Test #21:

score: 0
Accepted
time: 53ms
memory: 8360kb

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: 48ms
memory: 8268kb

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

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

result:

ok correct!

Test #24:

score: 0
Accepted
time: 42ms
memory: 7912kb

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: 151ms
memory: 10988kb

input:

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

output:

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

result:

ok correct!

Test #26:

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

input:

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

output:

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

result:

ok correct!

Test #27:

score: 0
Accepted
time: 84ms
memory: 9072kb

input:

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

output:

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

result:

ok correct!

Test #28:

score: 0
Accepted
time: 55ms
memory: 8592kb

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: 52ms
memory: 8468kb

input:

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

output:

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

result:

ok correct!

Test #30:

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

input:

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

output:

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

result:

ok correct!

Test #31:

score: 0
Accepted
time: 19ms
memory: 7680kb

input:

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

output:

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

result:

ok correct!

Test #32:

score: 0
Accepted
time: 55ms
memory: 8840kb

input:

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

output:

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

result:

ok correct!

Test #33:

score: 0
Accepted
time: 109ms
memory: 10284kb

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

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

result:

ok correct!

Test #36:

score: 0
Accepted
time: 43ms
memory: 8060kb

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: 58ms
memory: 8464kb

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: 28ms
memory: 7712kb

input:

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

output:

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

result:

ok correct!

Test #39:

score: 0
Accepted
time: 76ms
memory: 9480kb

input:

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

output:

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

result:

ok correct!

Test #40:

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

input:

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

output:

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

result:

ok correct!

Test #41:

score: 0
Accepted
time: 21ms
memory: 7488kb

input:

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

output:

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

result:

ok correct!

Test #42:

score: 0
Accepted
time: 73ms
memory: 8988kb

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: 133ms
memory: 10336kb

input:

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

output:

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

result:

ok correct!

Test #44:

score: 0
Accepted
time: 60ms
memory: 8852kb

input:

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

output:

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

result:

ok correct!

Test #45:

score: 0
Accepted
time: 31ms
memory: 7632kb

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: 52ms
memory: 8552kb

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: 98ms
memory: 8916kb

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: 46ms
memory: 8188kb

input:

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

output:

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

result:

ok correct!

Test #49:

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

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: 82ms
memory: 9248kb

input:

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

output:

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

result:

ok correct!

Test #51:

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

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: 33ms
memory: 7932kb

input:

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

output:

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

result:

ok correct!

Test #53:

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

input:

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

output:

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

result:

ok correct!

Test #54:

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

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: 91ms
memory: 9324kb

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: 39ms
memory: 7960kb

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: 77ms
memory: 9172kb

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: 35ms
memory: 7776kb

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: 133ms
memory: 10436kb

input:

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

output:

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

result:

ok correct!

Test #60:

score: 0
Accepted
time: 68ms
memory: 9320kb

input:

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

output:

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

result:

ok correct!

Test #61:

score: 0
Accepted
time: 34ms
memory: 7840kb

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: 54ms
memory: 8308kb

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: 81ms
memory: 9036kb

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

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

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

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

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

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

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

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

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

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

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

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

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

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

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

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

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

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

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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

result:

ok correct!

Test #74:

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

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: 14ms
memory: 7252kb

input:

1 4
.
.
X
.

output:

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

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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

result:

ok correct!

Test #77:

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

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: 9ms
memory: 7340kb

input:

1 4
X
X
X
.

output:

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

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

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

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

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

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

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

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

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

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

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

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

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

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

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

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

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

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

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

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

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

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

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

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

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

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

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

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

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

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

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

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

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

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

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

result:

ok correct!

Test #114:

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

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: 7ms
memory: 7256kb

input:

4 1
XXX.

output:

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

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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

result:

ok correct!

Test #120:

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

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: 12ms
memory: 7244kb

input:

4 1
X.XX

output:

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

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

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

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

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

result:

ok correct!

Test #124:

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

input:

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

output:

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

result:

ok correct!

Test #125:

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

input:

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

output:

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

result:

ok correct!

Test #126:

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

input:

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

output:

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

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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

result:

ok correct!

Test #128:

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

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: 17ms
memory: 7304kb

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: 15ms
memory: 7224kb

input:

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

output:

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

result:

ok correct!

Test #131:

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

input:

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

output:

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

result:

ok correct!

Test #132:

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

input:

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

output:

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

result:

ok correct!

Test #133:

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

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: 11ms
memory: 7240kb

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: 17ms
memory: 7476kb

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: 15ms
memory: 7232kb

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: 70ms
memory: 11196kb

input:

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

output:

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

result:

ok correct!

Test #138:

score: 0
Accepted
time: 59ms
memory: 11344kb

input:

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

output:

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

result:

ok correct!

Test #139:

score: 0
Accepted
time: 136ms
memory: 11296kb

input:

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

output:

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

result:

ok correct!

Test #140:

score: 0
Accepted
time: 146ms
memory: 11120kb

input:

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

output:

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

result:

ok correct!

Test #141:

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

input:

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

output:

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

result:

ok correct!

Test #142:

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

input:

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

output:

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

result:

ok correct!

Test #143:

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

input:

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

output:

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

result:

ok correct!

Test #144:

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

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: 43ms
memory: 8292kb

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: 156ms
memory: 11112kb

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed