QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393055#5112. Where Am I?shepherdAC ✓898ms75984kbC++206.7kb2024-04-18 06:18:282024-04-18 06:18:29

Judging History

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

  • [2024-04-18 06:18:29]
  • 评测
  • 测评结果:AC
  • 用时:898ms
  • 内存:75984kb
  • [2024-04-18 06:18:28]
  • 提交

answer

#include <bits/stdc++.h>

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

using namespace std;

#define len(a) static_cast<int>((a).size())
#define present(c, x) (c.find(x) != c.end())
#define printDecimal(d) std::cout << std::setprecision(d) << std::fixed

using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr const int iinf = 1e9 + 7;
constexpr const ll inf = 1e18;
constexpr const ll mod = 1'000'000'007;


struct TrieNode {
  int num_s{0}, weight{0};
  array<int, 2> children{-1, -1};
  pair<int, int> last_start;
};

static constexpr const int dx[] = {-1, 0, 1, 0};
static constexpr const int dy[] = {0, 1, 0, -1};

int n, m;
int grid[100][100];
vector<pair<int, int>> moves[10000];
array<vector<pair<int, int>>, 2> part;

vector<pair<int, int>> traverse_grid(int x, int y) {
  int nptr = 0, sz = n * m;
  int top = x, bottom = x, left = y, right = y;
  vector<pair<int, int>> compressed{make_pair(grid[x][y], 1)};
  for (int num_steps = 1; num_steps < sz;) {
    switch (nptr) {
      case 0: {
        top--;
        for (int i = bottom - 1; i >= top && num_steps < sz; i--) {
          if (i >= 0 && i < n && left >= 0 && left < m) {
            if (compressed.empty() ||
                compressed.back().first != grid[i][left]) {
              compressed.emplace_back(grid[i][left], 1);
            } else {
              compressed.back().second++;
            }
            num_steps++;
          } else {
            if (compressed.empty() || compressed.back().first != 0) {
              compressed.emplace_back(0, 1);
            } else {
              compressed.back().second++;
            }
          }
        }
        break;
      }
      case 1: {
        right++;
        for (int i = left + 1; i <= right && num_steps < sz; i++) {
          if (i >= 0 && i < m && top >= 0 && top < n) {
            if (compressed.empty() || compressed.back().first != grid[top][i]) {
              compressed.emplace_back(grid[top][i], 1);
            } else {
              compressed.back().second++;
            }
            num_steps++;
          } else {
            if (compressed.empty() || compressed.back().first != 0) {
              compressed.emplace_back(0, 1);
            } else {
              compressed.back().second++;
            }
          }
        }
        break;
      }
      case 2: {
        bottom++;
        for (int i = top + 1; i <= bottom && num_steps < sz; i++) {
          if (i >= 0 && i < n && right >= 0 && right < m) {
            if (compressed.empty() ||
                compressed.back().first != grid[i][right]) {
              compressed.emplace_back(grid[i][right], 1);
            } else {
              compressed.back().second++;
            }
            num_steps++;
          } else {
            if (compressed.empty() || compressed.back().first != 0) {
              compressed.emplace_back(0, 1);
            } else {
              compressed.back().second++;
            }
          }
        }
        break;
      }
      case 3: {
        left--;
        for (int i = right - 1; i >= left && num_steps < sz; i--) {
          if (i >= 0 && i < m && bottom >= 0 && bottom < n) {
            if (compressed.empty() ||
                compressed.back().first != grid[bottom][i]) {
              compressed.emplace_back(grid[bottom][i], 1);
            } else {
              compressed.back().second++;
            }
            num_steps++;
          } else {
            if (compressed.empty() || compressed.back().first != 0) {
              compressed.emplace_back(0, 1);
            } else {
              compressed.back().second++;
            }
          }
        }
        break;
      }
      default: {
        assert(false);
      }
    }
    nptr = (nptr + 1) % 4;
  }
  return compressed;
}

int main() {
  std::ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> m >> n;
  for (int i = 0; i < n; i++) {
    string line;
    cin >> line;
    for (int j = 0; j < m; j++) {
      if (line[j] == 'X') grid[i][j] = 1;
    }
  }
  vector<vector<int>> idx(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      moves[i * m + j] = traverse_grid(i, j);
      part[moves[i * m + j][0].first].emplace_back(i, j);
    }
  }
  vector<TrieNode> nodes(1);
  queue<pair<int, array<vector<pair<int, int>>, 2>>> q;
  q.emplace(0, part);
  while (!q.empty()) {
    auto [ptr, curr] = q.front();
    q.pop();
    for (int v = 0; v < 2; v++) {
      if (!curr[v].empty()) {
        array<vector<pair<int, int>>, 2> next;
        nodes.emplace_back();
        nodes[ptr].children[v] = len(nodes) - 1;
        int min_dist = iinf;
        for (const auto& [i, j] : curr[v]) {
          min_dist = min(min_dist, moves[i * m + j][idx[i][j]].second);
        }
        nodes[nodes[ptr].children[v]].weight = min_dist;
        nodes[nodes[ptr].children[v]].num_s = len(curr[v]);
        for (const auto& [i, j] : curr[v]) {
          moves[i * m + j][idx[i][j]].second -= min_dist;
          nodes[nodes[ptr].children[v]].last_start = make_pair(i, j);
          if (moves[i * m + j][idx[i][j]].second == 0) {
            if (++idx[i][j] < len(moves[i * m + j]))
              next[v ^ 1].emplace_back(i, j);
          } else {
            next[v].emplace_back(i, j);
          }
        }
        q.emplace(nodes[ptr].children[v], next);
      }
    }
  }

  int max_depth = 0;
  queue<pair<int, int>> qq;
  qq.emplace(0, 0);
  vector<pair<int, int>> furthest;
  unordered_map<int, int> cnt;
  while (!qq.empty()) {
    auto [curr, depth] = qq.front();
    qq.pop();
    if (nodes[curr].num_s == 1) {
      cnt[depth]++;
      if (max_depth < depth) {
        max_depth = depth;
        furthest = {make_pair(nodes[curr].last_start.second + 1,
                              n - nodes[curr].last_start.first)};
      } else if (max_depth == depth) {
        furthest.emplace_back(nodes[curr].last_start.second + 1,
                              n - nodes[curr].last_start.first);
      }
      continue;
    }
    for (int v = 0; v < 2; v++) {
      if (nodes[curr].children[v] != -1) {
        qq.emplace(nodes[curr].children[v], depth + nodes[curr].weight);
      }
    }
  }

  double e = 0.0;
  for (const auto& [k, v] : cnt) {
    e += double(k * v) / double(n * m);
  }
  printDecimal(3) << e << '\n' << max_depth << '\n';
  sort(furthest.begin(), furthest.end(), [](auto x, auto y) {
    if (x.second != y.second) return x.second < y.second;
    return x.first < y.first;
  });
  for (const auto& [x, y] : furthest) {
    cout << "(" << x << "," << y << ") ";
  }
  cout << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3968kb

input:

1 1
X

output:

0.000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

score: 0
Accepted
time: 778ms
memory: 74588kb

input:

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

output:

4757.947
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 876ms
memory: 5040kb

input:

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

output:

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

result:

ok correct!

Test #10:

score: 0
Accepted
time: 898ms
memory: 5160kb

input:

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

output:

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

result:

ok correct!

Test #11:

score: 0
Accepted
time: 683ms
memory: 49484kb

input:

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

output:

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

result:

ok correct!

Test #12:

score: 0
Accepted
time: 705ms
memory: 49768kb

input:

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

output:

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

result:

ok correct!

Test #13:

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

input:

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

output:

50.098
80
(7,6) (16,6) (20,12) (7,15) (16,15) (7,24) (16,24) (7,33) (16,33) (7,42) (16,42) (19,46) (12,47) (20,47) (7,51) (16,51) (12,56) (19,56) (7,60) (16,60) (20,65) (20,67) (7,69) (16,69) 

result:

ok correct!

Test #14:

score: 0
Accepted
time: 153ms
memory: 36828kb

input:

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

output:

100.711
742
(1,1) (2,1) 

result:

ok correct!

Test #15:

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

input:

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

output:

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

result:

ok correct!

Test #16:

score: 0
Accepted
time: 179ms
memory: 36488kb

input:

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

output:

122.545
387
(1,19) (19,32) 

result:

ok correct!

Test #17:

score: 0
Accepted
time: 97ms
memory: 22664kb

input:

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

output:

103.487
334
(10,57) (11,57) 

result:

ok correct!

Test #18:

score: 0
Accepted
time: 278ms
memory: 20588kb

input:

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

output:

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

result:

ok correct!

Test #19:

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

input:

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

output:

79.149
319
(1,39) (1,40) 

result:

ok correct!

Test #20:

score: 0
Accepted
time: 303ms
memory: 34536kb

input:

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

output:

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

result:

ok correct!

Test #21:

score: 0
Accepted
time: 219ms
memory: 21724kb

input:

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

output:

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

result:

ok correct!

Test #22:

score: 0
Accepted
time: 187ms
memory: 21436kb

input:

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

output:

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

result:

ok correct!

Test #23:

score: 0
Accepted
time: 101ms
memory: 12696kb

input:

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

output:

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

result:

ok correct!

Test #24:

score: 0
Accepted
time: 134ms
memory: 20892kb

input:

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

output:

152.162
512
(48,9) (48,67) 

result:

ok correct!

Test #25:

score: 0
Accepted
time: 782ms
memory: 74736kb

input:

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

output:

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

result:

ok correct!

Test #26:

score: 0
Accepted
time: 476ms
memory: 37000kb

input:

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

output:

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

result:

ok correct!

Test #27:

score: 0
Accepted
time: 395ms
memory: 42756kb

input:

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

output:

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

result:

ok correct!

Test #28:

score: 0
Accepted
time: 231ms
memory: 37744kb

input:

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

output:

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

result:

ok correct!

Test #29:

score: 0
Accepted
time: 261ms
memory: 35576kb

input:

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

output:

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

result:

ok correct!

Test #30:

score: 0
Accepted
time: 415ms
memory: 13828kb

input:

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

output:

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

result:

ok correct!

Test #31:

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

input:

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

output:

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

result:

ok correct!

Test #32:

score: 0
Accepted
time: 307ms
memory: 38756kb

input:

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

output:

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

result:

ok correct!

Test #33:

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

input:

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

output:

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

result:

ok correct!

Test #34:

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

input:

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

output:

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

result:

ok correct!

Test #35:

score: 0
Accepted
time: 130ms
memory: 20348kb

input:

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

output:

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

result:

ok correct!

Test #36:

score: 0
Accepted
time: 137ms
memory: 23060kb

input:

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

output:

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

result:

ok correct!

Test #37:

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

input:

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

output:

81.670
314
(1,64) (1,65) 

result:

ok correct!

Test #38:

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

input:

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

output:

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

result:

ok correct!

Test #39:

score: 0
Accepted
time: 579ms
memory: 37828kb

input:

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

output:

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

result:

ok correct!

Test #40:

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

input:

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

output:

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

result:

ok correct!

Test #41:

score: 0
Accepted
time: 284ms
memory: 8632kb

input:

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

output:

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

result:

ok correct!

Test #42:

score: 0
Accepted
time: 364ms
memory: 41468kb

input:

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

output:

225.089
803
(10,61) (11,61) 

result:

ok correct!

Test #43:

score: 0
Accepted
time: 665ms
memory: 73548kb

input:

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

output:

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

result:

ok correct!

Test #44:

score: 0
Accepted
time: 394ms
memory: 35964kb

input:

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

output:

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

result:

ok correct!

Test #45:

score: 0
Accepted
time: 62ms
memory: 21260kb

input:

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

output:

67.355
645
(1,1) (2,1) 

result:

ok correct!

Test #46:

score: 0
Accepted
time: 138ms
memory: 36232kb

input:

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

output:

80.041
332
(64,34) (65,34) 

result:

ok correct!

Test #47:

score: 0
Accepted
time: 220ms
memory: 38224kb

input:

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

output:

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

result:

ok correct!

Test #48:

score: 0
Accepted
time: 250ms
memory: 22296kb

input:

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

output:

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

result:

ok correct!

Test #49:

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

input:

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

output:

150.347
930
(52,44) (53,44) 

result:

ok correct!

Test #50:

score: 0
Accepted
time: 608ms
memory: 38624kb

input:

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

output:

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

result:

ok correct!

Test #51:

score: 0
Accepted
time: 193ms
memory: 21860kb

input:

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

output:

356.975
1620
(23,68) (51,68) 

result:

ok correct!

Test #52:

score: 0
Accepted
time: 569ms
memory: 21448kb

input:

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

output:

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

result:

ok correct!

Test #53:

score: 0
Accepted
time: 398ms
memory: 7800kb

input:

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

output:

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

result:

ok correct!

Test #54:

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

input:

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

output:

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

result:

ok correct!

Test #55:

score: 0
Accepted
time: 392ms
memory: 65756kb

input:

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

output:

179.279
713
(98,56) (98,57) 

result:

ok correct!

Test #56:

score: 0
Accepted
time: 74ms
memory: 20716kb

input:

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

output:

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

result:

ok correct!

Test #57:

score: 0
Accepted
time: 278ms
memory: 38280kb

input:

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

output:

115.941
390
(15,48) (79,48) 

result:

ok correct!

Test #58:

score: 0
Accepted
time: 102ms
memory: 22440kb

input:

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

output:

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

result:

ok correct!

Test #59:

score: 0
Accepted
time: 614ms
memory: 71420kb

input:

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

output:

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

result:

ok correct!

Test #60:

score: 0
Accepted
time: 545ms
memory: 39092kb

input:

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

output:

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

result:

ok correct!

Test #61:

score: 0
Accepted
time: 120ms
memory: 21320kb

input:

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

output:

164.878
772
(1,7) (1,8) 

result:

ok correct!

Test #62:

score: 0
Accepted
time: 181ms
memory: 37792kb

input:

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

output:

106.013
560
(1,1) (1,2) 

result:

ok correct!

Test #63:

score: 0
Accepted
time: 301ms
memory: 39304kb

input:

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

output:

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

result:

ok correct!

Test #64:

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

input:

1 2
X
X

output:

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

result:

ok correct!

Test #65:

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

input:

1 3
X
.
.

output:

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

result:

ok correct!

Test #66:

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

input:

1 3
.
X
.

output:

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

result:

ok correct!

Test #67:

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

input:

1 3
X
X
.

output:

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

result:

ok correct!

Test #68:

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

input:

1 3
.
.
X

output:

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

result:

ok correct!

Test #69:

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

input:

1 3
X
.
X

output:

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

result:

ok correct!

Test #70:

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

input:

1 3
.
X
X

output:

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

result:

ok correct!

Test #71:

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

input:

1 3
X
X
X

output:

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

result:

ok correct!

Test #72:

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

input:

1 4
X
.
.
.

output:

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

result:

ok correct!

Test #73:

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

input:

1 4
.
X
.
.

output:

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

result:

ok correct!

Test #74:

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

input:

1 4
X
X
.
.

output:

1.000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #75:

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

input:

1 4
.
.
X
.

output:

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

result:

ok correct!

Test #76:

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

input:

1 4
X
.
X
.

output:

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

result:

ok correct!

Test #77:

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

input:

1 4
.
X
X
.

output:

1.000
1
(1,1) (1,2) (1,3) (1,4) 

result:

ok correct!

Test #78:

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

input:

1 4
X
X
X
.

output:

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

result:

ok correct!

Test #79:

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

input:

1 4
.
.
.
X

output:

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

result:

ok correct!

Test #80:

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

input:

1 4
X
.
.
X

output:

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

result:

ok correct!

Test #81:

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

input:

1 4
.
X
.
X

output:

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

result:

ok correct!

Test #82:

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

input:

1 4
X
X
.
X

output:

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

result:

ok correct!

Test #83:

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

input:

1 4
.
.
X
X

output:

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

result:

ok correct!

Test #84:

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

input:

1 4
X
.
X
X

output:

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

result:

ok correct!

Test #85:

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

input:

1 4
.
X
X
X

output:

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

result:

ok correct!

Test #86:

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

input:

1 4
X
X
X
X

output:

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

result:

ok correct!

Test #87:

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

input:

2 2
X.
..

output:

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

result:

ok correct!

Test #88:

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

input:

2 2
.X
..

output:

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

result:

ok correct!

Test #89:

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

input:

2 2
XX
..

output:

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

result:

ok correct!

Test #90:

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

input:

2 2
..
X.

output:

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

result:

ok correct!

Test #91:

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

input:

2 2
X.
X.

output:

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

result:

ok correct!

Test #92:

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

input:

2 2
.X
X.

output:

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

result:

ok correct!

Test #93:

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

input:

2 2
XX
X.

output:

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

result:

ok correct!

Test #94:

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

input:

2 2
..
.X

output:

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

result:

ok correct!

Test #95:

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

input:

2 2
X.
.X

output:

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

result:

ok correct!

Test #96:

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

input:

2 2
.X
.X

output:

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

result:

ok correct!

Test #97:

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

input:

2 2
XX
.X

output:

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

result:

ok correct!

Test #98:

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

input:

2 2
..
XX

output:

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

result:

ok correct!

Test #99:

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

input:

2 2
X.
XX

output:

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

result:

ok correct!

Test #100:

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

input:

2 2
.X
XX

output:

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

result:

ok correct!

Test #101:

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

input:

2 2
XX
XX

output:

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

result:

ok correct!

Test #102:

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

input:

3 1
X..

output:

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

result:

ok correct!

Test #103:

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

input:

3 1
.X.

output:

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

result:

ok correct!

Test #104:

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

input:

3 1
XX.

output:

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

result:

ok correct!

Test #105:

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

input:

3 1
..X

output:

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

result:

ok correct!

Test #106:

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

input:

3 1
X.X

output:

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

result:

ok correct!

Test #107:

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

input:

3 1
.XX

output:

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

result:

ok correct!

Test #108:

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

input:

3 1
XXX

output:

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

result:

ok correct!

Test #109:

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

input:

4 1
X...

output:

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

result:

ok correct!

Test #110:

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

input:

4 1
.X..

output:

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

result:

ok correct!

Test #111:

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

input:

4 1
XX..

output:

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

result:

ok correct!

Test #112:

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

input:

4 1
..X.

output:

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

result:

ok correct!

Test #113:

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

input:

4 1
X.X.

output:

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

result:

ok correct!

Test #114:

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

input:

4 1
.XX.

output:

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

result:

ok correct!

Test #115:

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

input:

4 1
XXX.

output:

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

result:

ok correct!

Test #116:

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

input:

4 1
...X

output:

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

result:

ok correct!

Test #117:

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

input:

4 1
X..X

output:

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

result:

ok correct!

Test #118:

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

input:

4 1
.X.X

output:

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

result:

ok correct!

Test #119:

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

input:

4 1
XX.X

output:

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

result:

ok correct!

Test #120:

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

input:

4 1
..XX

output:

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

result:

ok correct!

Test #121:

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

input:

4 1
X.XX

output:

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

result:

ok correct!

Test #122:

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

input:

4 1
.XXX

output:

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

result:

ok correct!

Test #123:

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

input:

4 1
XXXX

output:

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

result:

ok correct!

Test #124:

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

input:

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

output:

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

result:

ok correct!

Test #125:

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

input:

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

output:

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

result:

ok correct!

Test #126:

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

input:

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

output:

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

result:

ok correct!

Test #127:

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

input:

100 1
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

output:

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

result:

ok correct!

Test #128:

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

input:

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

output:

3554.940
9950
(49,1) (51,1) 

result:

ok correct!

Test #129:

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

input:

100 2
X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.
.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X

output:

3451.070
9751
(49,1) (51,1) 

result:

ok correct!

Test #130:

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

input:

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

output:

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

result:

ok correct!

Test #131:

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

input:

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

output:

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

result:

ok correct!

Test #132:

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

input:

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

output:

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

result:

ok correct!

Test #133:

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

input:

1 100
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

output:

3406.500
9850
(1,50) (1,51) 

result:

ok correct!

Test #134:

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

input:

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

output:

3503.020
9850
(1,50) (1,52) 

result:

ok correct!

Test #135:

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

input:

2 100
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
X.
.X
...

output:

3401.110
9654
(2,49) (2,51) 

result:

ok correct!

Test #136:

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

input:

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

output:

58.080
95
(5,10) (6,10) 

result:

ok correct!

Test #137:

score: 0
Accepted
time: 835ms
memory: 37548kb

input:

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

output:

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

result:

ok correct!

Test #138:

score: 0
Accepted
time: 747ms
memory: 25588kb

input:

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

output:

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

result:

ok correct!

Test #139:

score: 0
Accepted
time: 760ms
memory: 24248kb

input:

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

output:

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

result:

ok correct!

Test #140:

score: 0
Accepted
time: 761ms
memory: 25376kb

input:

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

output:

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

result:

ok correct!

Test #141:

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

input:

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

output:

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

result:

ok correct!

Test #142:

score: 0
Accepted
time: 877ms
memory: 5064kb

input:

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

output:

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

result:

ok correct!

Test #143:

score: 0
Accepted
time: 877ms
memory: 5108kb

input:

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

output:

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

result:

ok correct!

Test #144:

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

input:

20 20
.XX......XX.....XXXX
..X.....X..X....X...
.....X..............
X..XX.X..XX......XX.
X..........X........
...X..X............X
.X...X..........XXXX
.X...XX..XX....X....
X.X.XX...X.......X.X
XXXXX....X........X.
.X.XX.X..XX...X.X...
X.......X..XXX.....X
.X..X..X.X......X...
.........X....X...X.
...

output:

12.812
31
(13,5) (15,18) 

result:

ok correct!

Test #145:

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

input:

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

output:

60.831
195
(28,1) (1,35) 

result:

ok correct!

Test #146:

score: 0
Accepted
time: 816ms
memory: 75984kb

input:

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

output:

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

result:

ok correct!

Extra Test:

score: 0
Extra Test Passed