QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88755 | #5112. Where Am I? | ItsJerr | WA | 113ms | 10560kb | C++14 | 2.6kb | 2023-03-17 00:13:04 | 2023-03-17 00:13:05 |
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 <= 120; ++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]), m - get<1>(v[i]) + 1);
res += ans;
}
cout << fixed << setprecision(5) << 1.0 * res / (m * n) << "\n";
cout << mx << "\n";
sort(points.begin(), points.end(), [&](const pair<int, int> &x, const pair<int, int> &y){
if (x.second == y.second) return x.first < y.first;
return x.second < y.second;
});
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: 14ms
memory: 7252kb
input:
1 1 X
output:
0.00000 0 (1,1)
result:
ok correct!
Test #2:
score: 0
Accepted
time: 3ms
memory: 7376kb
input:
2 1 .X
output:
0.00000 0 (1,1) (2,1)
result:
ok correct!
Test #3:
score: 0
Accepted
time: 15ms
memory: 7260kb
input:
2 1 X.
output:
0.00000 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: 0
Accepted
time: 8ms
memory: 7260kb
input:
1 2 . X
output:
0.00000 0 (1,1) (1,2)
result:
ok correct!
Test #5:
score: 0
Accepted
time: 8ms
memory: 7244kb
input:
1 2 X .
output:
0.00000 0 (1,1) (1,2)
result:
ok correct!
Test #6:
score: 0
Accepted
time: 10ms
memory: 7256kb
input:
2 1 XX
output:
3.00000 3 (1,1) (2,1)
result:
ok correct!
Test #7:
score: 0
Accepted
time: 14ms
memory: 7348kb
input:
3 3 XXX X.X XXX
output:
3.11111 5 (3,1) (3,2)
result:
ok correct!
Test #8:
score: -100
Wrong Answer
time: 113ms
memory: 10560kb
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:
4880.51110 9950 (3,1) (3,100)
result:
wrong answer read 4880.511100 but expected 4757.947100, error = 122.564000