QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#393056 | #5112. Where Am I? | shepherd | AC ✓ | 839ms | 75872kb | C++20 | 7.1kb | 2024-04-18 06:23:15 | 2024-04-18 06:23:16 |
Judging History
answer
#include <bits/stdc++.h>
#pragma GCC optimize("O3, unroll-loops")
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;
template <typename Fun>
class y_combinator_result {
Fun fun_;
public:
template <typename T>
explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {}
template <typename... Args>
decltype(auto) operator()(Args&&... args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <typename Fun>
decltype(auto) y_combinator(Fun&& fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
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;
void traverse_grid(int x, int y) {
int nptr = 0, sz = n * m;
int top = x, bottom = x, left = y, right = y;
int pos = x * m + y;
auto& compressed = moves[pos];
compressed.emplace_back(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;
}
}
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++) {
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: 4104kb
input:
1 1 X
output:
0.000 0 (1,1)
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
2 1 .X
output:
0.000 0 (1,1) (2,1)
result:
ok correct!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
2 1 X.
output:
0.000 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 2 . X
output:
0.000 0 (1,1) (1,2)
result:
ok correct!
Test #5:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
1 2 X .
output:
0.000 0 (1,1) (1,2)
result:
ok correct!
Test #6:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
2 1 XX
output:
3.000 3 (1,1) (2,1)
result:
ok correct!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
3 3 XXX X.X XXX
output:
3.111 5 (3,1) (3,2)
result:
ok correct!
Test #8:
score: 0
Accepted
time: 707ms
memory: 74604kb
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: 828ms
memory: 5152kb
input:
100 100 X................................................................................................... .................................................................................................... .............................................................................................
output:
19735.320 39599 (100,1) (100,2)
result:
ok correct!
Test #10:
score: 0
Accepted
time: 837ms
memory: 5308kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
19865.670 39500 (100,1) (100,2)
result:
ok correct!
Test #11:
score: 0
Accepted
time: 670ms
memory: 49244kb
input:
100 100 X................................................................................................... .X.................................................................................................. ..X..........................................................................................
output:
11855.639 39302 (100,99) (99,100)
result:
ok correct!
Test #12:
score: 0
Accepted
time: 660ms
memory: 50924kb
input:
100 100 ...................................................................................................X ..................................................................................................X. .............................................................................................
output:
11854.610 39104 (1,99) (2,100)
result:
ok correct!
Test #13:
score: 0
Accepted
time: 58ms
memory: 14264kb
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: 141ms
memory: 36416kb
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: 76ms
memory: 8172kb
input:
56 59 ........................................................ ........................................................ ........................................................ ........................................................ ........................................................ X...........
output:
494.498 1503 (56,38) (56,39)
result:
ok correct!
Test #16:
score: 0
Accepted
time: 190ms
memory: 37824kb
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: 87ms
memory: 23092kb
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: 248ms
memory: 20572kb
input:
64 91 ................................................................ ................................................................ ................................................................ ................................................................ .....................................
output:
480.573 1215 (64,71) (63,91)
result:
ok correct!
Test #19:
score: 0
Accepted
time: 135ms
memory: 35660kb
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: 293ms
memory: 34492kb
input:
97 54 .............X................................................................................... ..................................X.............................................................. ....X............................................................................................ ...
output:
383.808 1084 (93,9) (51,51)
result:
ok correct!
Test #21:
score: 0
Accepted
time: 214ms
memory: 22264kb
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: 180ms
memory: 20768kb
input:
80 55 .............................................................X.................. ................................................................................ .................................................................XX............. ..............................................X.......
output:
176.083 611 (80,2) (79,37)
result:
ok correct!
Test #23:
score: 0
Accepted
time: 100ms
memory: 12252kb
input:
61 59 ...........X................................................. ............................................................. .......................................................X..... ............................................................. ...............................X.................
output:
291.706 860 (1,1) (1,50)
result:
ok correct!
Test #24:
score: 0
Accepted
time: 125ms
memory: 21176kb
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: 747ms
memory: 74012kb
input:
100 96 .................................................................X.................................. .............................X...................................................................... ..............................................................................................
output:
212.396 1031 (1,67) (1,68)
result:
ok correct!
Test #26:
score: 0
Accepted
time: 456ms
memory: 38436kb
input:
94 84 .............................................................................................. .............................................................................................. .............................................................................................. ............
output:
357.121 2687 (1,83) (1,84)
result:
ok correct!
Test #27:
score: 0
Accepted
time: 372ms
memory: 43704kb
input:
86 80 ...........................................................X..........X............... ...................................................................................... X..................................................................................... ....................................
output:
225.856 975 (84,1) (85,1)
result:
ok correct!
Test #28:
score: 0
Accepted
time: 221ms
memory: 38172kb
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: 249ms
memory: 35396kb
input:
65 85 ................................................................. ................................................................. ................................................................. ...................X............................................. .................................
output:
738.974 3378 (5,45) (5,56)
result:
ok correct!
Test #30:
score: 0
Accepted
time: 392ms
memory: 12824kb
input:
76 98 ............................................................................ ............................................................................ ............................................................................ ..................................................................
output:
1550.391 4192 (76,34) (76,96)
result:
ok correct!
Test #31:
score: 0
Accepted
time: 119ms
memory: 8924kb
input:
62 67 .............................................................. .............................................................. .........................X.................................... ...................................................X.......... .............................................
output:
648.650 2420 (16,1) (1,13)
result:
ok correct!
Test #32:
score: 0
Accepted
time: 290ms
memory: 38412kb
input:
50 98 ..........................................X....... .................................X...............X .................................................. .................................................. .............................................X.... ..........................................
output:
207.338 895 (1,97) (1,98)
result:
ok correct!
Test #33:
score: 0
Accepted
time: 495ms
memory: 69576kb
input:
74 97 ....................X..................................................... .......................................................................... .......................................................................... ................................X.......................................
output:
193.030 1078 (74,70) (71,93)
result:
ok correct!
Test #34:
score: 0
Accepted
time: 160ms
memory: 5932kb
input:
62 77 .............................................................. .............................................................. .............................................................. .............................................................. .............................................
output:
2021.070 4937 (46,73) (8,77)
result:
ok correct!
Test #35:
score: 0
Accepted
time: 120ms
memory: 20936kb
input:
47 74 ............................................... ............................................... ............................................... .....................X......................... ............................................... ............................................X.. .........
output:
142.154 673 (1,74) (2,74)
result:
ok correct!
Test #36:
score: 0
Accepted
time: 127ms
memory: 23180kb
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: 137ms
memory: 36004kb
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: 169ms
memory: 13416kb
input:
40 93 .......X................................ ........................................ ........................................ ........................................ .X...................................... ..................X..................... ........................................ ..........
output:
300.308 1326 (39,93) (40,93)
result:
ok correct!
Test #39:
score: 0
Accepted
time: 541ms
memory: 39524kb
input:
87 99 ....................................................................................... ....................................................................................... ....................................................................................... .................................
output:
474.069 2063 (1,1) (49,1)
result:
ok correct!
Test #40:
score: 0
Accepted
time: 191ms
memory: 5736kb
input:
46 94 .............................................. .............................................. .............................................. .............................................. .............................................. .............................................. ...............
output:
2555.367 5914 (46,1) (46,2)
result:
ok correct!
Test #41:
score: 0
Accepted
time: 264ms
memory: 8584kb
input:
93 60 ............................................................................................. ............................................................................................. ............................................................................................. ...............
output:
2389.200 11288 (21,60) (22,60)
result:
ok correct!
Test #42:
score: 0
Accepted
time: 352ms
memory: 40904kb
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: 630ms
memory: 71668kb
input:
94 95 .............................................................................................. .......................................................X...................................... ............X................................................X.......................X........ ............
output:
213.688 941 (33,89) (33,90)
result:
ok correct!
Test #44:
score: 0
Accepted
time: 363ms
memory: 36404kb
input:
94 72 .............................................................................................. .............................................................................................. .............................................................................................. ............
output:
1330.090 4671 (60,71) (38,72)
result:
ok correct!
Test #45:
score: 0
Accepted
time: 48ms
memory: 20084kb
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: 135ms
memory: 35812kb
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: 195ms
memory: 37216kb
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: 232ms
memory: 22840kb
input:
87 60 ....................................................................................... ........................................................................X.............. ....................................................................................... .................................
output:
302.790 799 (87,29) (87,58)
result:
ok correct!
Test #49:
score: 0
Accepted
time: 55ms
memory: 12924kb
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: 579ms
memory: 39132kb
input:
94 97 .............................................................................................. .......................................X......................X............................... .............................................................................................. ............
output:
690.646 3826 (1,96) (1,97)
result:
ok correct!
Test #51:
score: 0
Accepted
time: 175ms
memory: 21340kb
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: 518ms
memory: 22236kb
input:
100 91 .................................................................................................... .................................................................................................... ..............................................................................................
output:
1705.102 4664 (100,44) (100,90)
result:
ok correct!
Test #53:
score: 0
Accepted
time: 369ms
memory: 7728kb
input:
88 84 ........................................................................................ ........................................................................................ ........................................................................................ ..............................
output:
2976.142 8305 (68,1) (69,1)
result:
ok correct!
Test #54:
score: 0
Accepted
time: 45ms
memory: 12536kb
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: 377ms
memory: 65376kb
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: 79ms
memory: 21280kb
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: 274ms
memory: 38208kb
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: 100ms
memory: 22380kb
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: 588ms
memory: 71008kb
input:
86 98 .......X......X....................................................................... ...................................................................................... ...................................................................................... ....................................
output:
215.501 732 (66,70) (68,72)
result:
ok correct!
Test #60:
score: 0
Accepted
time: 518ms
memory: 38080kb
input:
91 94 ........................................................................................... ........................................................................................... ........................................................................................... .....................
output:
309.110 1541 (78,1) (90,8)
result:
ok correct!
Test #61:
score: 0
Accepted
time: 118ms
memory: 19900kb
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: 162ms
memory: 36708kb
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: 286ms
memory: 39168kb
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: 3868kb
input:
1 3 X . .
output:
0.667 1 (1,1) (1,2)
result:
ok correct!
Test #66:
score: 0
Accepted
time: 0ms
memory: 4116kb
input:
1 3 . X .
output:
0.667 1 (1,1) (1,3)
result:
ok correct!
Test #67:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
1 3 X X .
output:
0.667 1 (1,2) (1,3)
result:
ok correct!
Test #68:
score: 0
Accepted
time: 0ms
memory: 3876kb
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: 3876kb
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: 3872kb
input:
1 4 . X . .
output:
2.750 5 (1,1) (1,4)
result:
ok correct!
Test #74:
score: 0
Accepted
time: 0ms
memory: 4040kb
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: 3880kb
input:
1 4 . . X .
output:
2.750 5 (1,3) (1,4)
result:
ok correct!
Test #76:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
1 4 X . X .
output:
7.500 10 (1,2) (1,4)
result:
ok correct!
Test #77:
score: 0
Accepted
time: 0ms
memory: 3876kb
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: 3880kb
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: 4012kb
input:
1 4 . . . X
output:
10.250 18 (1,3) (1,4)
result:
ok correct!
Test #80:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
1 4 X . . X
output:
14.000 27 (1,1) (1,4)
result:
ok correct!
Test #81:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
1 4 . X . X
output:
5.500 10 (1,1) (1,3)
result:
ok correct!
Test #82:
score: 0
Accepted
time: 0ms
memory: 3880kb
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: 4116kb
input:
1 4 . . X X
output:
3.000 5 (1,3) (1,4)
result:
ok correct!
Test #84:
score: 0
Accepted
time: 0ms
memory: 3812kb
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: 3880kb
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: 3876kb
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: 3972kb
input:
2 2 X. ..
output:
3.750 7 (2,1) (2,2)
result:
ok correct!
Test #88:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
2 2 .X ..
output:
1.250 2 (1,1) (1,2)
result:
ok correct!
Test #89:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
2 2 XX ..
output:
2.500 3 (1,2) (2,2)
result:
ok correct!
Test #90:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
2 2 .. X.
output:
4.250 6 (2,1) (2,2)
result:
ok correct!
Test #91:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
2 2 X. X.
output:
3.500 6 (2,1) (2,2)
result:
ok correct!
Test #92:
score: 0
Accepted
time: 0ms
memory: 4104kb
input:
2 2 .X X.
output:
1.500 2 (1,1) (2,2)
result:
ok correct!
Test #93:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 2 XX X.
output:
1.750 3 (1,2) (2,2)
result:
ok correct!
Test #94:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
2 2 .. .X
output:
2.750 4 (1,2) (2,2)
result:
ok correct!
Test #95:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
2 2 X. .X
output:
2.500 4 (2,1) (1,2)
result:
ok correct!
Test #96:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
2 2 .X .X
output:
1.500 2 (1,1) (1,2)
result:
ok correct!
Test #97:
score: 0
Accepted
time: 0ms
memory: 3884kb
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: 3876kb
input:
2 2 X. XX
output:
2.250 4 (2,1) (1,2)
result:
ok correct!
Test #100:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
2 2 .X XX
output:
1.250 2 (1,1) (2,2)
result:
ok correct!
Test #101:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
2 2 XX XX
output:
2.500 3 (1,2) (2,2)
result:
ok correct!
Test #102:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
3 1 X..
output:
4.667 7 (2,1) (3,1)
result:
ok correct!
Test #103:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
3 1 .X.
output:
2.000 3 (1,1) (3,1)
result:
ok correct!
Test #104:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
3 1 XX.
output:
2.000 3 (1,1) (2,1)
result:
ok correct!
Test #105:
score: 0
Accepted
time: 0ms
memory: 3876kb
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: 3932kb
input:
3 1 .XX
output:
2.000 3 (2,1) (3,1)
result:
ok correct!
Test #108:
score: 0
Accepted
time: 0ms
memory: 4100kb
input:
3 1 XXX
output:
5.667 7 (1,1) (2,1)
result:
ok correct!
Test #109:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
4 1 X...
output:
12.750 22 (3,1) (4,1)
result:
ok correct!
Test #110:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
4 1 .X..
output:
4.250 7 (3,1) (4,1)
result:
ok correct!
Test #111:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
4 1 XX..
output:
5.000 7 (3,1) (4,1)
result:
ok correct!
Test #112:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
4 1 ..X.
output:
4.250 7 (1,1) (4,1)
result:
ok correct!
Test #113:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
4 1 X.X.
output:
8.500 14 (1,1) (3,1)
result:
ok correct!
Test #114:
score: 0
Accepted
time: 0ms
memory: 4008kb
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: 3820kb
input:
4 1 XXX.
output:
4.250 7 (1,1) (2,1)
result:
ok correct!
Test #116:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
4 1 ...X
output:
7.750 14 (1,1) (2,1)
result:
ok correct!
Test #117:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
4 1 X..X
output:
18.000 33 (1,1) (4,1)
result:
ok correct!
Test #118:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
4 1 .X.X
output:
10.500 14 (2,1) (4,1)
result:
ok correct!
Test #119:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
4 1 XX.X
output:
4.250 7 (2,1) (4,1)
result:
ok correct!
Test #120:
score: 0
Accepted
time: 0ms
memory: 4108kb
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: 3936kb
input:
4 1 X.XX
output:
4.250 7 (1,1) (4,1)
result:
ok correct!
Test #122:
score: 0
Accepted
time: 0ms
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: 4128kb
input:
4 1 XXXX
output:
9.500 14 (2,1) (3,1)
result:
ok correct!
Test #124:
score: 0
Accepted
time: 2ms
memory: 4028kb
input:
100 1 X...................................................................................................
output:
13274.590 38710 (99,1) (100,1)
result:
ok correct!
Test #125:
score: 0
Accepted
time: 5ms
memory: 3948kb
input:
100 1 ...................................................................................................X
output:
13076.630 38318 (1,1) (2,1)
result:
ok correct!
Test #126:
score: 0
Accepted
time: 5ms
memory: 3940kb
input:
100 1 ..................................................X.................................................
output:
3356.010 9751 (1,1) (100,1)
result:
ok correct!
Test #127:
score: 0
Accepted
time: 6ms
memory: 4488kb
input:
100 1 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
output:
3457.500 9950 (50,1) (51,1)
result:
ok correct!
Test #128:
score: 0
Accepted
time: 3ms
memory: 4132kb
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: 4648kb
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: 3936kb
input:
1 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X
output:
13175.610 38514 (1,99) (1,100)
result:
ok correct!
Test #132:
score: 0
Accepted
time: 5ms
memory: 3940kb
input:
1 100 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
output:
3306.030 9653 (1,99) (1,100)
result:
ok correct!
Test #133:
score: 0
Accepted
time: 6ms
memory: 4388kb
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: 4272kb
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: 4828kb
input:
2 100 X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X X. .X ...
output:
3401.110 9654 (2,49) (2,51)
result:
ok correct!
Test #136:
score: 0
Accepted
time: 0ms
memory: 3984kb
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: 701ms
memory: 37024kb
input:
100 100 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX .................................................................................................... .............................................................................................
output:
13878.927 38908 (99,1) (100,1)
result:
ok correct!
Test #138:
score: 0
Accepted
time: 701ms
memory: 25348kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
14059.272 39302 (99,100) (100,100)
result:
ok correct!
Test #139:
score: 0
Accepted
time: 707ms
memory: 24580kb
input:
100 100 X................................................................................................... X................................................................................................... X............................................................................................
output:
14132.282 39500 (100,1) (100,2)
result:
ok correct!
Test #140:
score: 0
Accepted
time: 714ms
memory: 25252kb
input:
100 100 ...................................................................................................X ...................................................................................................X .............................................................................................
output:
13951.433 39104 (1,99) (1,100)
result:
ok correct!
Test #141:
score: 0
Accepted
time: 839ms
memory: 5072kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
19733.340 39302 (99,100) (100,100)
result:
ok correct!
Test #142:
score: 0
Accepted
time: 832ms
memory: 5136kb
input:
100 100 ...................................................................................................X .................................................................................................... .............................................................................................
output:
19601.010 39104 (1,99) (1,100)
result:
ok correct!
Test #143:
score: 0
Accepted
time: 839ms
memory: 5124kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
5001.490 10098 (99,100) (100,100)
result:
ok correct!
Test #144:
score: 0
Accepted
time: 8ms
memory: 5744kb
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: 84ms
memory: 21588kb
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: 795ms
memory: 75872kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
227.535 1062 (96,95) (55,100)
result:
ok correct!
Extra Test:
score: 0
Extra Test Passed