QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#393055 | #5112. Where Am I? | shepherd | AC ✓ | 898ms | 75984kb | C++20 | 6.7kb | 2024-04-18 06:18:28 | 2024-04-18 06:18:29 |
Judging History
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';
}
詳細信息
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