QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#408734#5112. Where Am I?berarchegasAC ✓176ms236064kbC++143.4kb2024-05-10 22:22:522024-05-10 22:22:52

Judging History

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

  • [2024-05-10 22:22:52]
  • 评测
  • 测评结果:AC
  • 用时:176ms
  • 内存:236064kb
  • [2024-05-10 22:22:52]
  • 提交

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;

void bt(vector<int>& v, int time) {
    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(bad,mn);
};

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

    

    bt(poss,0);

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

input:

1 1
X

output:

0.000000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

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

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

input:

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

output:

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

result:

ok correct!

Test #10:

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

input:

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

output:

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

result:

ok correct!

Test #11:

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

input:

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

output:

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

result:

ok correct!

Test #12:

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

input:

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

output:

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

result:

ok correct!

Test #13:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #16:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #19:

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

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

input:

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

output:

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

result:

ok correct!

Test #21:

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

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #26:

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

input:

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

output:

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

result:

ok correct!

Test #27:

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

input:

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

output:

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

result:

ok correct!

Test #28:

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

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

input:

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

output:

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

result:

ok correct!

Test #30:

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

input:

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

output:

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

result:

ok correct!

Test #31:

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

input:

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

output:

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

result:

ok correct!

Test #32:

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

input:

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

output:

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

result:

ok correct!

Test #33:

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

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

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

input:

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

output:

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

result:

ok correct!

Test #36:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #39:

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

input:

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

output:

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

result:

ok correct!

Test #40:

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

input:

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

output:

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

result:

ok correct!

Test #41:

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

input:

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

output:

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

result:

ok correct!

Test #42:

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

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

input:

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

output:

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

result:

ok correct!

Test #44:

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

input:

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

output:

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

result:

ok correct!

Test #45:

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #49:

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

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

input:

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

output:

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

result:

ok correct!

Test #51:

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

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

input:

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

output:

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

result:

ok correct!

Test #53:

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

input:

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

output:

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

result:

ok correct!

Test #54:

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

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

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

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: 7ms
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: 9116kb

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

input:

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

output:

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

result:

ok correct!

Test #60:

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

input:

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

output:

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

result:

ok correct!

Test #61:

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

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

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

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

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

input:

1 3
.
X
.

output:

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

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

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

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

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

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

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

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

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

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

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

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

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

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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

result:

ok correct!

Test #74:

score: 0
Accepted
time: 0ms
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: 0ms
memory: 8212kb

input:

1 4
.
.
X
.

output:

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

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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

result:

ok correct!

Test #77:

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

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

input:

1 4
X
X
X
.

output:

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

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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

result:

ok correct!

Test #80:

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

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

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

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

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

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

input:

1 4
X
X
X
X

output:

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

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

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

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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

result:

ok correct!

Test #93:

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

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

input:

2 2
X.
.X

output:

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

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

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

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

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

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

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

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

score: 0
Accepted
time: 0ms
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: 8140kb

input:

3 1
X.X

output:

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

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

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

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

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

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

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

result:

ok correct!

Test #114:

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

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

input:

4 1
XXX.

output:

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

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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

result:

ok correct!

Test #120:

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

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

input:

4 1
X.XX

output:

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

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

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

result:

ok correct!

Test #123:

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

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

input:

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

output:

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

result:

ok correct!

Test #126:

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

input:

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

output:

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

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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

result:

ok correct!

Test #128:

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

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

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

input:

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

output:

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

result:

ok correct!

Test #131:

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

input:

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

output:

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

result:

ok correct!

Test #132:

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

input:

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

output:

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

result:

ok correct!

Test #133:

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

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

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

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

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

input:

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

output:

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

result:

ok correct!

Test #138:

score: 0
Accepted
time: 70ms
memory: 88928kb

input:

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

output:

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

result:

ok correct!

Test #139:

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

input:

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

output:

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

result:

ok correct!

Test #140:

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

input:

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

output:

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

result:

ok correct!

Test #141:

score: 0
Accepted
time: 171ms
memory: 235872kb

input:

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

output:

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

result:

ok correct!

Test #142:

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

input:

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

output:

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

result:

ok correct!

Test #143:

score: 0
Accepted
time: 176ms
memory: 236064kb

input:

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

output:

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

result:

ok correct!

Test #144:

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

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

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

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed