QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91034 | #5112. Where Am I? | vk1cd314 | WA | 3ms | 3656kb | C++20 | 2.7kb | 2023-03-26 19:34:29 | 2023-03-26 19:34:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m; scanf("%d %d", &n, &m);
vector <vector <char>> a(n, vector <char>(m));
for (auto &v : a) for (auto &c : v) scanf(" %c", &c);
vector <int> dirx, diry;
vector <pair <int, int>> xs;
int sx = 0, sy = 0;
bool dir = true;
dirx.push_back(0), diry.push_back(0);
for (int i = 0, j = 1; i < 2 * 105; ++i, ++j, dir ^= 1) {
if (dir) {
for (int k = 0; k < j; ++k) dirx.push_back(--sx), diry.push_back(sy);
for (int k = 0; k < j; ++k) dirx.push_back(sx), diry.push_back(++sy);
} else {
for (int k = 0; k < j; ++k) dirx.push_back(++sx), diry.push_back(sy);
for (int k = 0; k < j; ++k) dirx.push_back(sx), diry.push_back(--sy);
}
}
auto ok = [&](int i, int j) {
if (!((0 <= i && i < n) && (0 <= j && j < m))) return false;
return a[i][j] == 'X';
};
vector <vector <vector <int>>> pos(n, vector <vector <int>>(m));
vector <pair <int, int>> all;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
vector <int> go;
for (int k = 0; k < (int) dirx.size(); ++k) {
int ni = i + dirx[k], nj = j + diry[k];
if (ok(ni, nj)) {
go.push_back(k);
}
}
pos[i][j] = go;
all.push_back({i, j});
}
}
sort(all.begin(), all.end(), [&](auto &a, auto &b) {
return pos[a.first][a.second] < pos[b.first][b.second];
});
auto get = [&](int i) {
if (i == 0 || i == n * m) return 0;
int match = 0;
auto [i2, j2] = all[i];
auto [i1, j1] = all[i - 1];
while (pos[i1][j1][match] == pos[i2][j2][match]) ++match;
return min(pos[i1][j1][match], pos[i2][j2][match]);
};
int max_ans = -1;
vector <pair <int, int>> mans;
long long tot = 0;
for (int i = 0; i < (int) all.size(); ++i) {
int add = max(get(i), get(i + 1));
if (add > max_ans) {
max_ans = add;
mans.clear();
mans.push_back(all[i]);
} else if (add == max_ans) {
mans.push_back(all[i]);
}
tot += add;
}
for (auto &[x, y] : mans) {
swap(x, y);
x = x + 1;
y = n - y;
}
sort(mans.begin(), mans.end(), [&](auto &a, auto &b) {
if (a.second == b.second) return a.second < b.second;
return a.first < b.first;
});
printf("%.3lf\n%d\n", (double) tot / (n * m), max_ans);
for (auto [x, y] : mans) printf("(%d,%d) ", x, y);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3656kb
input:
1 1 X
output:
0.000 0 (1,1)
result:
ok correct!
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3652kb
input:
2 1 .X
output:
0.000 0 (1,1) (1,2)
result:
wrong answer Read (1,2) but expected (2,1)