QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408727#5112. Where Am I?berarchegasAC ✓180ms235984kbC++143.5kb2024-05-10 22:01:422024-05-10 22:01:42

Judging History

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

  • [2024-05-10 22:01:42]
  • 评测
  • 测评结果:AC
  • 用时:180ms
  • 内存:235984kb
  • [2024-05-10 22:01:42]
  • 提交

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)];

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);

    double expected = 0;
    int mx = 0;

    vector<int> mxocur;

    auto bt =[&](vector<int>& v, int time, auto && bt) -> void {
        if(v.size() == 1){
            expected+=time;
            if(mx < time){
                mx = time;
                mxocur.clear();
            }
            if(mx == time){
                mxocur.push_back(v.back());
            }
            return;
        }
        if(v.size() == 0){
            return;
        }
        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();

        bt(good,mn,bt);
        bt(bad,mn,bt);
    };

    bt(poss,0,bt);

    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;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 8156kb

input:

1 1
X

output:

0.000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

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

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

input:

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

output:

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

result:

ok correct!

Test #10:

score: 0
Accepted
time: 173ms
memory: 235952kb

input:

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

output:

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

result:

ok correct!

Test #11:

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

input:

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

output:

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

result:

ok correct!

Test #12:

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

input:

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

output:

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

result:

ok correct!

Test #13:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #16:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

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

input:

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

output:

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

result:

ok correct!

Test #21:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #24:

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

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

input:

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

output:

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

result:

ok correct!

Test #26:

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

input:

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

output:

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

result:

ok correct!

Test #27:

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

input:

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

output:

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

result:

ok correct!

Test #28:

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

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

input:

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

output:

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

result:

ok correct!

Test #30:

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

input:

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

output:

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

result:

ok correct!

Test #31:

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

input:

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

output:

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

result:

ok correct!

Test #32:

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

input:

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

output:

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

result:

ok correct!

Test #33:

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

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

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

result:

ok correct!

Test #36:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #39:

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

input:

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

output:

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

result:

ok correct!

Test #40:

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

input:

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

output:

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

result:

ok correct!

Test #41:

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

input:

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

output:

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

result:

ok correct!

Test #42:

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

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

input:

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

output:

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

result:

ok correct!

Test #44:

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

input:

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

output:

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

result:

ok correct!

Test #45:

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #49:

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

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

input:

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

output:

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

result:

ok correct!

Test #51:

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

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

input:

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

output:

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

result:

ok correct!

Test #53:

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

input:

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

output:

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

result:

ok correct!

Test #54:

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

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

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

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

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

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

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

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

result:

ok correct!

Test #67:

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

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

input:

1 3
X
.
X

output:

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

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

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

result:

ok correct!

Test #71:

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

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

input:

1 4
X
.
.
.

output:

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

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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

result:

ok correct!

Test #74:

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

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

input:

1 4
.
.
X
.

output:

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

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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

result:

ok correct!

Test #77:

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

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

input:

1 4
X
X
X
.

output:

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

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

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

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

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

result:

ok correct!

Test #82:

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

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

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

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

input:

1 4
.
X
X
X

output:

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

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

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

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

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

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

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

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

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

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

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

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

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

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

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

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

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

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

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

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

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

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

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

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

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

result:

ok correct!

Test #114:

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

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

input:

4 1
XXX.

output:

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

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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

result:

ok correct!

Test #120:

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

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

input:

4 1
X.XX

output:

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

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

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

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

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

result:

ok correct!

Test #124:

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

input:

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

output:

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

result:

ok correct!

Test #125:

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

input:

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

output:

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

result:

ok correct!

Test #126:

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

input:

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

output:

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

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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

result:

ok correct!

Test #128:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #131:

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

input:

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

output:

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

result:

ok correct!

Test #132:

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

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #138:

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

input:

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

output:

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

result:

ok correct!

Test #139:

score: 0
Accepted
time: 81ms
memory: 89096kb

input:

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

output:

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

result:

ok correct!

Test #140:

score: 0
Accepted
time: 80ms
memory: 88940kb

input:

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

output:

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

result:

ok correct!

Test #141:

score: 0
Accepted
time: 164ms
memory: 235904kb

input:

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

output:

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

result:

ok correct!

Test #142:

score: 0
Accepted
time: 164ms
memory: 235952kb

input:

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

output:

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

result:

ok correct!

Test #143:

score: 0
Accepted
time: 180ms
memory: 235984kb

input:

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

output:

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

result:

ok correct!

Test #144:

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

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

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed