QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408739#5112. Where Am I?berarchegasAC ✓204ms8584kbC++143.6kb2024-05-10 22:44:362024-05-10 22:44:36

Judging History

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

  • [2024-05-10 22:44:36]
  • 评测
  • 测评结果:AC
  • 用时:204ms
  • 内存:8584kb
  • [2024-05-10 22:44:36]
  • 提交

answer

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
 
mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
    
const int MOD = 1e9 + 7;
const int MAXN = 5e6 + 5;
const int INF = 1e9;

template<typename T>
using matrix = vector<vector<T>>;
using point = complex<int>;


vector<int> lista [int(1e4+5)];

double expected = 0;
int mx = 0;

vector<int> mxocur;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> m >> n;

    for(int i = 0; i < 1e4+5; i++)
        lista[i].reserve(101);

    vector<point> mark;

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            char c;
            cin >> c;
            if(c == 'X')
                mark.push_back(point(i,j));
        }
    }


    auto get_val =[&](point p) -> int {
        if(p.real() == 0 && p.imag() == 0)
            return 0;
        p = point(p.imag(), p.real());
        int d = max(abs(p.real()), abs(p.imag()));
        int sq = (d*2-1)*(d*2-1);

        if(p.real() == -1*d){
            return sq+6*d-p.imag()+d-1;
        }
        if(p.imag() == d){
            return sq+4*d-p.real()+d-1;
        }
        if(p.real() == d){
            return sq+2*d + p.imag()+d-1; 
        }
        return sq + p.real() + d-1;
    };

    // for(int i = -3; i <= 3; i++){
    //     for(int j = -3; j <= 3; j++){
    //         cout << point(i,j) << ' ' << get_val(point(i,j)) << '\n';
    //     }
    // }




    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            for(int k = 0; k < mark.size(); k++){
                point cur = mark[k] - point(i,j);
                lista[i*m+j].push_back(get_val(cur));
            }
            lista[i*m+j].push_back(INF);
            sort(all(lista[i*m+j]),greater<int>());

            // cerr << point(i,j) << ": ";
            // for(int k : lista[i*m+j])
            //     cerr << k << ' ';
            // cerr << endl;
        }
    }
    const int l = max(n,m);
    const int lim = l*l*5+10;

    vector<int> poss(n*m);
    iota(all(poss),0);

    vector<pair<vector<int>,int>> q;
    q.push_back(make_pair(poss,0));

    while(!q.empty()){
        auto [v, time] = q.back();
        q.pop_back();

        if(v.size() == 1){
            expected+=time;
            if(mx < time){
                mx = time;
                mxocur.clear();
            }
            if(mx == time){
                mxocur.push_back(v.back());
            }
            continue;
        }
        if(v.size() == 0){
            continue;
        }
        int mn = INF;   

        for(int i : v){
            mn = min(mn, lista[i].back());
        }

        vector<int> good, bad;

        for(int i : v){
            if(lista[i].back() == mn){
                lista[i].pop_back();
                good.push_back(i);
            } else {
                bad.push_back(i);
            }
        }

        v.clear();

        q.push_back(make_pair(good,mn));
        q.push_back(make_pair(bad,mn));     
    }

    expected/=n*m;

    cout << fixed << setprecision(6) << expected << '\n' << mx << '\n';

    vector<point> resp;
    for(int k : mxocur)
        resp.push_back(point(k%m+1, n-k/m));

    sort(all(resp), [&](point a, point b){
        if(a.imag() == b.imag())
            return a.real() < b.real();
        return a.imag() < b.imag();
    });

    for(auto p : resp)
        cout << p << ' ';
    cout << '\n';


    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 1
X

output:

0.000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

0.000000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

0.000000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

0.000000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

0.000000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

3.000000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

3.111111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 25ms
memory: 8380kb

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.947100
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 204ms
memory: 8572kb

input:

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

output:

19735.319900
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

score: 0
Accepted
time: 203ms
memory: 8568kb

input:

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

output:

19865.669900
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: 0
Accepted
time: 24ms
memory: 8376kb

input:

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

output:

11855.639200
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

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

input:

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

output:

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

result:

ok correct!

Test #13:

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

input:

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

output:

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

input:

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

output:

100.711201
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

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

input:

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

output:

494.497881
1503
(56,38) (56,39) 

result:

ok correct!

Test #16:

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

input:

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

output:

122.545312
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

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

input:

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

output:

103.487444
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

input:

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

output:

79.149333
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

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

input:

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

output:

383.808324
1084
(93,9) (51,51) 

result:

ok correct!

Test #21:

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

input:

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

output:

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

result:

ok correct!

Test #22:

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

input:

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

output:

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

result:

ok correct!

Test #23:

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

input:

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

output:

291.706029
860
(1,1) (1,50) 

result:

ok correct!

Test #24:

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

input:

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

output:

152.161881
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

score: 0
Accepted
time: 25ms
memory: 8484kb

input:

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

output:

212.396250
1031
(1,67) (1,68) 

result:

ok correct!

Test #26:

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

input:

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

output:

357.121327
2687
(1,83) (1,84) 

result:

ok correct!

Test #27:

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

input:

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

output:

225.855523
975
(84,1) (85,1) 

result:

ok correct!

Test #28:

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

input:

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

output:

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

result:

ok correct!

Test #29:

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

input:

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

output:

738.974480
3378
(5,45) (5,56) 

result:

ok correct!

Test #30:

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

input:

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

output:

1550.390977
4192
(76,34) (76,96) 

result:

ok correct!

Test #31:

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

input:

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

output:

648.650217
2420
(16,1) (1,13) 

result:

ok correct!

Test #32:

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

input:

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

output:

207.337755
895
(1,97) (1,98) 

result:

ok correct!

Test #33:

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

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

142.153824
673
(1,74) (2,74) 

result:

ok correct!

Test #36:

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

input:

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

output:

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

result:

ok correct!

Test #37:

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

input:

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

output:

81.669985
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

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

input:

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

output:

300.307527
1326
(39,93) (40,93) 

result:

ok correct!

Test #39:

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

input:

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

output:

474.068966
2063
(1,1) (49,1) 

result:

ok correct!

Test #40:

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

input:

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

output:

2555.367484
5914
(46,1) (46,2) 

result:

ok correct!

Test #41:

score: 0
Accepted
time: 25ms
memory: 8580kb

input:

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

output:

2389.200358
11288
(21,60) (22,60) 

result:

ok correct!

Test #42:

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

input:

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

output:

225.089160
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

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

input:

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

output:

213.687570
941
(33,89) (33,90) 

result:

ok correct!

Test #44:

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

input:

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

output:

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

result:

ok correct!

Test #45:

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

input:

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

output:

67.354743
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

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

input:

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

output:

80.041026
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

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

input:

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

output:

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

result:

ok correct!

Test #48:

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

input:

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

output:

302.789847
799
(87,29) (87,58) 

result:

ok correct!

Test #49:

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

input:

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

output:

150.346913
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

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

input:

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

output:

690.646414
3826
(1,96) (1,97) 

result:

ok correct!

Test #51:

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

input:

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

output:

356.974580
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

score: 0
Accepted
time: 24ms
memory: 8512kb

input:

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

output:

1705.102198
4664
(100,44) (100,90) 

result:

ok correct!

Test #53:

score: 0
Accepted
time: 40ms
memory: 8300kb

input:

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

output:

2976.142316
8305
(68,1) (69,1) 

result:

ok correct!

Test #54:

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

input:

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

output:

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

result:

ok correct!

Test #55:

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

input:

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

output:

179.279252
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

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

input:

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

output:

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

result:

ok correct!

Test #57:

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

input:

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

output:

115.940570
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

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

input:

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

output:

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

result:

ok correct!

Test #59:

score: 0
Accepted
time: 23ms
memory: 8376kb

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

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

input:

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

output:

164.878078
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

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

input:

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

output:

106.012938
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

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

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

1.000000
1
(1,1) (1,2) 

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

0.666667
1
(1,1) (1,2) 

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

0.666667
1
(1,1) (1,3) 

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

0.666667
1
(1,2) (1,3) 

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

3.333333
5
(1,2) (1,3) 

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

6.666667
10
(1,1) (1,3) 

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

0.666667
1
(1,1) (1,2) 

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

3.666667
5
(1,1) (1,2) 

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

5.250000
10
(1,1) (1,2) 

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

2.750000
5
(1,1) (1,4) 

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

2.750000
5
(1,3) (1,4) 

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

7.500000
10
(1,2) (1,4) 

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.000000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

2.750000
5
(1,2) (1,3) 

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

10.250000
18
(1,3) (1,4) 

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

14.000000
27
(1,1) (1,4) 

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

5.500000
10
(1,1) (1,3) 

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

2.750000
5
(1,1) (1,4) 

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

3.000000
5
(1,3) (1,4) 

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

2.750000
5
(1,2) (1,4) 

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

2.750000
5
(1,1) (1,2) 

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

6.500000
10
(1,2) (1,3) 

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

3.750000
7
(2,1) (2,2) 

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

1.250000
2
(1,1) (1,2) 

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

2.500000
3
(1,2) (2,2) 

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

4.250000
6
(2,1) (2,2) 

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

3.500000
6
(2,1) (2,2) 

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

1.500000
2
(1,1) (2,2) 

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

1.750000
3
(1,2) (2,2) 

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

2.750000
4
(1,2) (2,2) 

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

2.500000
4
(2,1) (1,2) 

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

1.500000
2
(1,1) (1,2) 

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

1.750000
3
(1,2) (2,2) 

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

3.500000
4
(1,2) (2,2) 

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

2.250000
4
(2,1) (1,2) 

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

1.250000
2
(1,1) (2,2) 

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

2.500000
3
(1,2) (2,2) 

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

4.666667
7
(2,1) (3,1) 

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

2.000000
3
(1,1) (3,1) 

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

2.000000
3
(1,1) (2,1) 

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

2.000000
3
(1,1) (2,1) 

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

9.333333
14
(1,1) (3,1) 

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

2.000000
3
(2,1) (3,1) 

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

5.666667
7
(1,1) (2,1) 

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

12.750000
22
(3,1) (4,1) 

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

4.250000
7
(3,1) (4,1) 

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

5.000000
7
(3,1) (4,1) 

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

4.250000
7
(1,1) (4,1) 

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

8.500000
14
(1,1) (3,1) 

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

3.000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

4.250000
7
(1,1) (2,1) 

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

7.750000
14
(1,1) (2,1) 

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

18.000000
33
(1,1) (4,1) 

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

10.500000
14
(2,1) (4,1) 

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

4.250000
7
(2,1) (4,1) 

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

3.000000
3
(1,1) (2,1) (3,1) (4,1) 

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

4.250000
7
(1,1) (4,1) 

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

4.250000
7
(2,1) (3,1) 

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

9.500000
14
(2,1) (3,1) 

result:

ok correct!

Test #124:

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

input:

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

output:

13274.590000
38710
(99,1) (100,1) 

result:

ok correct!

Test #125:

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

input:

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

output:

13076.630000
38318
(1,1) (2,1) 

result:

ok correct!

Test #126:

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

input:

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

output:

3356.010000
9751
(1,1) (100,1) 

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

3457.500000
9950
(50,1) (51,1) 

result:

ok correct!

Test #128:

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

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.940000
9950
(49,1) (51,1) 

result:

ok correct!

Test #129:

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

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.070000
9751
(49,1) (51,1) 

result:

ok correct!

Test #130:

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

input:

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

output:

12977.650000
38122
(1,1) (1,2) 

result:

ok correct!

Test #131:

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

input:

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

output:

13175.610000
38514
(1,99) (1,100) 

result:

ok correct!

Test #132:

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

input:

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

output:

3306.030000
9653
(1,99) (1,100) 

result:

ok correct!

Test #133:

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

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.500000
9850
(1,50) (1,51) 

result:

ok correct!

Test #134:

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

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.020000
9850
(1,50) (1,52) 

result:

ok correct!

Test #135:

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

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.110000
9654
(2,49) (2,51) 

result:

ok correct!

Test #136:

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

input:

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

output:

58.080000
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

score: 0
Accepted
time: 75ms
memory: 8468kb

input:

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

output:

13878.927500
38908
(99,1) (100,1) 

result:

ok correct!

Test #138:

score: 0
Accepted
time: 83ms
memory: 8420kb

input:

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

output:

14059.272500
39302
(99,100) (100,100) 

result:

ok correct!

Test #139:

score: 0
Accepted
time: 79ms
memory: 8508kb

input:

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

output:

14132.282500
39500
(100,1) (100,2) 

result:

ok correct!

Test #140:

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

input:

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

output:

13951.432500
39104
(1,99) (1,100) 

result:

ok correct!

Test #141:

score: 0
Accepted
time: 203ms
memory: 8460kb

input:

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

output:

19733.339900
39302
(99,100) (100,100) 

result:

ok correct!

Test #142:

score: 0
Accepted
time: 178ms
memory: 8584kb

input:

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

output:

19601.009900
39104
(1,99) (1,100) 

result:

ok correct!

Test #143:

score: 0
Accepted
time: 198ms
memory: 8572kb

input:

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

output:

5001.489900
10098
(99,100) (100,100) 

result:

ok correct!

Test #144:

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

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.812500
31
(13,5) (15,18) 

result:

ok correct!

Test #145:

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

input:

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

output:

60.830800
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed