QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87834#5112. Where Am I?zokerAC ✓596ms8832kbC++174.0kb2023-03-14 15:00:422023-03-14 15:00:44

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-14 15:00:44]
  • 评测
  • 测评结果:AC
  • 用时:596ms
  • 内存:8832kb
  • [2023-03-14 15:00:42]
  • 提交

answer

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

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")

using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;

#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V> 
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
#else
#define dbg(...) 7
#endif

#define eb emplace_back
#define fi first
#define se second

const ll INFL = 2e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T, class V> 
ostream& operator << (ostream &s, pair<T, V> a){
	s << a.fi << ' ' << a.se; return s;
}

template<class T, class V> 
istream& operator >> (istream &s, pair<T, V> &a){
	s >> a.fi >> a.se; return s;
}

template<class T> 
ostream& operator << (ostream &s, vector<T> a){
	for(int i = 0; i < (int)a.size(); i++){
		if(i > 0)s << ' ' ; 
		s << a[i];
	} return s;
}

template<class T> 
istream& operator >> (istream &s, vector<T> &a){
	for(T &x : a)s >> x; 
	return s;
}

template<class T> 
void input(T a[], int l, int r, istream &s = cin){
	while(l <= r)s >> a[l++];
}

template<class T> 
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
	while(l <= r){ s << a[l++];
		if(l <= r) s << ' ';
	} if(en)s << "\n";
}



const int N = 1e2+3, K = 26;
//====================================================================//

vector<int> L(1, -1), R(1, -1), cnt(1, 0);
string grid[N];
int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};
void testcase(){
	int n, m;
	cin >> m >> n;
	int tot = 0;
	for(int i = 0; i < n; i++)cin >> grid[i], tot += count(grid[i].begin(), grid[i].end(), 'X');
	vector<pair<vector<int>, int>> all;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			all.eb();
			all.back().se = i * m + j;
			int curI = i, curJ = j;
			int k = 1, l = 2, p = 0, t = 0, mov = 0;
			if(grid[i][j] == 'X')all.back().fi.eb(0);
			while(all.back().fi.size() < tot){
				curI += di[p];
				curJ += dj[p];
				mov++;
				if(curI >= 0 && curI < n && curJ >= 0 && curJ < m && grid[curI][curJ] == 'X')all.back().fi.eb(mov);
				t++;
				if(t == k){
					l--;
					t = 0;
					p = (p + 1) & 3;
					if(l == 0)l = 2, k++;
				}
				//dbg(i, j);
			}
		}
	}
	sort(all.begin(), all.end());
	vector<int> ans(all.size());
	auto solve = [&](auto &&solve, int mov, int l, int r, int ind){
		if(l == r){
			if(mov)mov--;
			ans[l] = mov;
			return;
		}
		int lo = l, hi = r + 1;
		while(lo < hi){
			int mid = lo + hi >> 1;
			if(all[mid].fi[ind] == mov)lo = mid + 1;
			else hi = mid;
		}
		if(l != lo)solve(solve, mov + 1, l, lo - 1, ind + 1);
		if(lo != r + 1)solve(solve, mov + 1, lo, r, ind);
	};
	
	solve(solve, 0, 0, all.size() - 1, 0);
	
	ld sum = accumulate(ans.begin(), ans.end(), 0LL);
	sum /= ans.size();
	cout << fixed << setprecision(3) << sum << "\n";
	int mx = *max_element(ans.begin(), ans.end());
	cout << mx << "\n";
	vii temp;
	for(int i = 0; i < ans.size(); i++){
		if(ans[i] == mx){
			temp.eb(n - all[i].se / m, all[i].se % m + 1);
		}
	}
	sort(temp.begin(), temp.end());
	for(int i = 0; i < temp.size(); i++){
		cout << "(" << temp[i].se << "," << temp[i].fi << ")" << " \n"[i + 1 == temp.size() ];
	}
	cout << "\n";
	
}





int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int T = 1;
	//cin >> T;
	
	for(int qq = 1; qq <= T; ++qq){
		//cout << "Case #" << qq << ": ";
		testcase();
	}
	return 0;
}
/*
6 1597352862016328480
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

1 1
X

output:

0.000
0
(1,1)


result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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


result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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


result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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


result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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


result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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


result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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


result:

ok correct!

Test #8:

score: 0
Accepted
time: 583ms
memory: 8832kb

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

input:

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

output:

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


result:

ok correct!

Test #10:

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

input:

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

output:

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


result:

ok correct!

Test #11:

score: 0
Accepted
time: 592ms
memory: 8332kb

input:

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

output:

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


result:

ok correct!

Test #12:

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

input:

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

output:

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


result:

ok correct!

Test #13:

score: 0
Accepted
time: 35ms
memory: 4416kb

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

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

input:

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

output:

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


result:

ok correct!

Test #16:

score: 0
Accepted
time: 128ms
memory: 5264kb

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

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

input:

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

output:

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


result:

ok correct!

Test #19:

score: 0
Accepted
time: 78ms
memory: 5136kb

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

input:

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

output:

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


result:

ok correct!

Test #21:

score: 0
Accepted
time: 157ms
memory: 4780kb

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

input:

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

output:

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


result:

ok correct!

Test #23:

score: 0
Accepted
time: 78ms
memory: 4160kb

input:

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

output:

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


result:

ok correct!

Test #24:

score: 0
Accepted
time: 89ms
memory: 4256kb

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

input:

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

output:

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


result:

ok correct!

Test #26:

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

input:

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

output:

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


result:

ok correct!

Test #27:

score: 0
Accepted
time: 277ms
memory: 6824kb

input:

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

output:

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


result:

ok correct!

Test #28:

score: 0
Accepted
time: 144ms
memory: 5628kb

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

input:

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

output:

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


result:

ok correct!

Test #30:

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

input:

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

output:

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


result:

ok correct!

Test #31:

score: 0
Accepted
time: 96ms
memory: 4028kb

input:

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

output:

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


result:

ok correct!

Test #32:

score: 0
Accepted
time: 223ms
memory: 6000kb

input:

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

output:

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


result:

ok correct!

Test #33:

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

input:

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

output:

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


result:

ok correct!

Test #34:

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

input:

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

output:

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


result:

ok correct!

Test #35:

score: 0
Accepted
time: 85ms
memory: 4416kb

input:

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

output:

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


result:

ok correct!

Test #36:

score: 0
Accepted
time: 82ms
memory: 4764kb

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

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

input:

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

output:

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


result:

ok correct!

Test #39:

score: 0
Accepted
time: 332ms
memory: 8024kb

input:

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

output:

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


result:

ok correct!

Test #40:

score: 0
Accepted
time: 117ms
memory: 3832kb

input:

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

output:

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


result:

ok correct!

Test #41:

score: 0
Accepted
time: 159ms
memory: 3860kb

input:

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

output:

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


result:

ok correct!

Test #42:

score: 0
Accepted
time: 251ms
memory: 6528kb

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

input:

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

output:

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


result:

ok correct!

Test #44:

score: 0
Accepted
time: 285ms
memory: 5356kb

input:

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

output:

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


result:

ok correct!

Test #45:

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

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

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

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

input:

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

output:

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


result:

ok correct!

Test #49:

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

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

input:

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

output:

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


result:

ok correct!

Test #51:

score: 0
Accepted
time: 128ms
memory: 4912kb

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

input:

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

output:

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


result:

ok correct!

Test #53:

score: 0
Accepted
time: 209ms
memory: 3964kb

input:

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

output:

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


result:

ok correct!

Test #54:

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

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

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

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

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

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

input:

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

output:

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


result:

ok correct!

Test #60:

score: 0
Accepted
time: 396ms
memory: 5904kb

input:

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

output:

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


result:

ok correct!

Test #61:

score: 0
Accepted
time: 89ms
memory: 4372kb

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

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

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

input:

1 2
X
X

output:

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


result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

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


result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

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


result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

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


result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

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


result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

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


result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

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


result:

ok correct!

Test #71:

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

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

input:

1 4
X
.
.
.

output:

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


result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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


result:

ok correct!

Test #74:

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

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

input:

1 4
.
.
X
.

output:

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


result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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


result:

ok correct!

Test #77:

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

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

input:

1 4
X
X
X
.

output:

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


result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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


result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

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


result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

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


result:

ok correct!

Test #82:

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

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

input:

1 4
.
.
X
X

output:

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


result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

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


result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

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


result:

ok correct!

Test #86:

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

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

input:

2 2
X.
..

output:

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


result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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


result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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


result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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


result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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


result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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


result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

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


result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

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


result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

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


result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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


result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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


result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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


result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

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


result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

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


result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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


result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

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


result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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


result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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


result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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


result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

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


result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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


result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

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


result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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


result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

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


result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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


result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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


result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

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


result:

ok correct!

Test #114:

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

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

input:

4 1
XXX.

output:

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


result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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


result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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


result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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


result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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


result:

ok correct!

Test #120:

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

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

input:

4 1
X.XX

output:

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


result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

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


result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

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


result:

ok correct!

Test #124:

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

input:

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

output:

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


result:

ok correct!

Test #125:

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

input:

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

output:

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


result:

ok correct!

Test #126:

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

input:

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

output:

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


result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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


result:

ok correct!

Test #128:

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

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

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

input:

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

output:

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


result:

ok correct!

Test #131:

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

input:

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

output:

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


result:

ok correct!

Test #132:

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

input:

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

output:

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


result:

ok correct!

Test #133:

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

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

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

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

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

input:

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

output:

13878.928
38908
(99,1) (100,1)


result:

ok correct!

Test #138:

score: 0
Accepted
time: 513ms
memory: 8700kb

input:

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

output:

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


result:

ok correct!

Test #139:

score: 0
Accepted
time: 510ms
memory: 8332kb

input:

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

output:

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


result:

ok correct!

Test #140:

score: 0
Accepted
time: 507ms
memory: 8636kb

input:

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

output:

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


result:

ok correct!

Test #141:

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

input:

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

output:

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


result:

ok correct!

Test #142:

score: 0
Accepted
time: 388ms
memory: 4000kb

input:

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

output:

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


result:

ok correct!

Test #143:

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

input:

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

output:

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


result:

ok correct!

Test #144:

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

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

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

input:

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

output:

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


result:

ok correct!

Extra Test:

score: 0
Extra Test Passed