QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#91036 | #5112. Where Am I? | vk1cd314 | RE | 212ms | 5416kb | C++20 | 2.7kb | 2023-03-26 19:41:26 | 2023-03-26 19:41:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m; scanf("%d %d", &m, &n);
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 < 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);
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3588kb
input:
1 1 X
output:
0.000 0 (1,1)
result:
ok correct!
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 1 .X
output:
0.000 0 (1,1) (2,1)
result:
ok correct!
Test #3:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
2 1 X.
output:
0.000 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
1 2 . X
output:
0.000 0 (1,1) (1,2)
result:
ok correct!
Test #5:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
1 2 X .
output:
0.000 0 (1,1) (1,2)
result:
ok correct!
Test #6:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
2 1 XX
output:
3.000 3 (1,1) (2,1)
result:
ok correct!
Test #7:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 3 XXX X.X XXX
output:
3.111 5 (3,1) (3,2)
result:
ok correct!
Test #8:
score: 0
Accepted
time: 212ms
memory: 5416kb
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: -100
Runtime Error
input:
100 100 X................................................................................................... .................................................................................................... .............................................................................................