QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#356537 | #5112. Where Am I? | TWTP_TCTF# | WA | 0ms | 4196kb | C++17 | 2.8kb | 2024-03-17 22:37:02 | 2024-03-17 22:37:03 |
Judging History
answer
#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define ll long long
#define ld long double
using namespace std;
const int N = 1e4 + 5, C = 5e4 + 7;
int mod = 998244353;
vector<int> dist[N];
int ans[N];
int n, m;
string s[105];
pair<int, int> getindex(int flat) {
return {flat / m, flat % m};
}
int flatten(int i, int j) {
return i * m + j;
}
int getdist(int a, int b, int x, int y) {
x -= a;
y -= b;
if (x == 0 && y == 0)return 0;
int p = max(abs(x), abs(y)) - 1;
int d = (2 * p + 1) * (2 * p + 1) - 1;
if (x == -p - 1 && y >= -p) {
return d + 1 + y - (-p);
}
d += 1 + 2 * p + 1;
if (y == p + 1) {
return d + x - (-p - 1);
}
d += 2 * p + 2;
if (x == p + 1) {
return d + p + 1 - y;
}
d += 2 * p + 2;
return d + p + 1 - x;
}
void pre() {
vector<pair<int, int>> xs;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
if (s[i][j] == 'X')
xs.push_back({i, j});
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
for (auto it: xs)
dist[flatten(i, j)].push_back(getdist(i, j, it.first, it.second));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
sort(dist[flatten(i, j)].rbegin(), dist[flatten(i, j)].rend());
}
void solve(vector<int> &indexs, bool del = 1) {
map<int, vector<int>> mp;
int mx1 = 0, mx2;
for (int i: indexs) {
if (del)
dist[i].pop_back();
if (dist[i].back() >= mx1) {
mx2 = mx1;
mx1 = dist[i].back();
} else if (dist[i].back() > mx2)
mx2 = dist[i].back();
mp[dist[i].back()].push_back(i);
}
for (auto it: mp) {
if (it.second.size() == 1)
ans[it.second[0]] = min(mx2, it.first);
else
solve(it.second);
}
}
ld calExp() {
ll total = 0;
for (int i = 0; i < n * m; ++i)
total += ans[i];
return (ld) total / (n * m);
}
int main() {
IO
cin >> m >> n;
for (int i = 0; i < n; ++i)
cin >> s[i];
pre();
vector<int> index;
for (int i = 0; i < n * m; ++i)
index.push_back(i);
solve(index, 0);
cout << fixed << setprecision(3) << calExp() << '\n';
int mx = 0;
for (int i = 0; i < n * m; ++i)
mx = max(mx, ans[i]);
cout << mx << '\n';
vector<pair<int, int>> tmp;
for (int i = 0; i < n * m; ++i) {
if (ans[i] == mx) {
auto p = getindex(i);
tmp.push_back({n - p.first, p.second + 1});
}
}
std::sort(tmp.begin(), tmp.end());
for (auto p: tmp) {
cout << "(" << p.second << ", " << p.first << ") ";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 4196kb
input:
1 1 X
output:
0.000 0 (1, 1)
result:
wrong answer Read (1, but expected (1,1)