QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88752 | #5112. Where Am I? | ItsJerr | WA | 8ms | 6268kb | C++14 | 2.4kb | 2023-03-17 00:08:48 | 2023-03-17 00:08:50 |
Judging History
answer
//source: https://qoj.ac/contest/1050/problem/5112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<pair<int, int>, int> idx;
void prep() {
int px = 0, py = 0, it = 0;
idx[make_pair(0, 0)] = 0;
for (int layer = 1; layer <= 100; ++layer) {
--px;
idx[make_pair(px, py)] = ++it;
for (int i = 1; i < 2 * layer; ++i) idx[make_pair(px, ++py)] = ++it;
for (int i = 1; i <= 2 * layer; ++i) idx[make_pair(++px, py)] = ++it;
for (int i = 1; i <= 2 * layer; ++i) idx[make_pair(px, --py)] = ++it;
for (int i = 1; i <= 2 * layer; ++i) idx[make_pair(--px, py)] = ++it;
}
}
const int N = 110;
char a[N][N];
signed main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("icpc_wf_f.inp", "r")) {
freopen("icpc_wf_f.inp", "r", stdin);
freopen("icpc_wf_f.out", "w", stdout);
}
#ifdef LOCAL_MACHINE
if (fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
#endif
prep();
int m, n; cin >> n >> m;
for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];
vector<pair<int, int>> marked;
for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (a[i][j] == 'X') marked.emplace_back(i, j);
vector<tuple<vector<int>, int, int>> v;
for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) {
vector<int> cur;
for (const pair<int, int> &p : marked) {
int u, v; tie(u, v) = p;
cur.push_back(idx[make_pair(u - i, v - j)]);
}
sort(cur.begin(), cur.end());
v.emplace_back(cur, i, j);
}
sort(v.begin(), v.end());
int res = 0, mx = 0;
vector<pair<int, int>> points;
for (int i = 0; i < m * n; ++i) {
int cur = 0, ans = 0;
if (i) {
for (int t = 0; t < marked.size(); ++t) {
if (get<0>(v[i])[t] == get<0>(v[i - 1])[t]) ++cur;
}
ans = max(ans, min(get<0>(v[i])[cur], get<0>(v[i - 1])[cur]));
}
cur = 0;
if (i + 1 < m * n) {
for (int t = 0; t < marked.size(); ++t) {
if (get<0>(v[i])[t] == get<0>(v[i + 1])[t]) ++cur;
}
ans = max(ans, min(get<0>(v[i])[cur], get<0>(v[i + 1])[cur]));
}
if (ans > mx) {
mx = ans;
points.clear();
}
if (ans == mx) points.emplace_back(get<2>(v[i]), n - get<1>(v[i]) + 1);
res += ans;
}
cout << fixed << setprecision(3) << 1.0 * res / (m * n) << "\n";
cout << mx << "\n";
for (const pair<int, int> &i : points) cout << "(" << i.first << "," << i.second << ") ";
}
// ඞඞඞඞඞ you sus
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 6268kb
input:
1 1 X
output:
0.000 0 (1,1)
result:
ok correct!
Test #2:
score: -100
Wrong Answer
time: 8ms
memory: 6136kb
input:
2 1 .X
output:
0.000 0 (2,2) (1,2)
result:
wrong answer Read (2,2) but expected (1,1)