QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373093 | #5112. Where Am I? | RobeZH# | WA | 2ms | 5876kb | C++23 | 3.1kb | 2024-04-01 02:16:22 | 2024-04-01 02:16:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define subnb true
#define Lnb true
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
struct P {
vi vs;
int x, y;
};
const int INF = (int)1e9;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
swap(n, m);
vector<string> str(n);
vector<pii> mks;
rep(i, 0, n) {
cin >> str[i];
rep(j, 0, m) {
if(str[i][j] == 'X') {
mks.push_back({i, j});
}
}
}
int C = 200;
vector<pii> ps;
vector<vi> seq(2 * C, vi(2 * C, 0));
int x = C, y = C;
auto in_bound = [&](int x, int y) {
return 0 <= x && x < 2 * C && 0 <= y && y < 2 * C;
};
auto mv_d = [&](int dx, int dy, int step) {
while(step--) {
seq[x][y] = sz(ps);
ps.push_back({x - C, y - C});
x += dx;
y += dy;
if(!in_bound(x, y)) return false;
}
return true;
};
for(int s = 1; ; s++) {
if(s % 2 == 1) {
if(!mv_d(-1, 0, s)) break;
if(!mv_d(0, 1, s)) break;
} else {
if(!mv_d(1, 0, s)) break;
if(!mv_d(0, -1, s)) break;
}
}
vector<P> xs;
rep(i, 0, n) {
rep(j, 0, m) {
vi vs;
for (auto p : mks) {
vs.push_back(seq[p.first - i + C][p.second - j + C]);
}
sort(all(vs));
xs.push_back({vs, i, j});
// cout << i << ", " << j << ": ";
// for (int y : vs) cout << y << " ";
// cout << endl;
}
}
sort(all(xs), [](const P &p1, const P &p2) {
return p1.vs < p2.vs;
});
vector<vi> res(n, vi(m));
vi lcp(sz(xs));
rep(i, 1, sz(xs)) {
int cur = 0;
while(xs[i].vs[cur] == xs[i - 1].vs[cur]) cur++;
lcp[i] = min(xs[i].vs[cur], xs[i - 1].vs[cur]);
// cout << i << ": " << lcp[i] << endl;
}
ll sum = 0;
int mx = 0;
vector<pii> mxs;
rep(i, 0, sz(xs)) {
int ans = max((i > 0 ? lcp[i] : 0), (i + 1 < sz(xs) ? lcp[i + 1] : 0));
// cout << lcp[i] << " " << lcp[i + 1] << ", " << ans << endl;
res[xs[i].x][xs[i].y] = ans;
// cout << xs[i].x << " " << xs[i].y << ": ";
// for (int x : xs[i].vs) cout << x << " ";
// cout << ", ans: " << ans << endl;
// cout << endl;
sum += ans;
if(ans > mx) {
mx = ans;
mxs = {{xs[i].y, xs[i].x }};
} else if(ans == mx) {
mxs.push_back({xs[i].y, xs[i].x});
}
}
ld ev = (ld)sum / n / m;
cout << fixed << setprecision(10) << ev << '\n';
cout << mx << '\n';
sort(all(mxs));
for (auto p : mxs) cout << "(" << p.first + 1 << "," << (n - 1 - p.second) + 1 << ") ";
cout << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 5800kb
input:
1 1 X
output:
0.0000000000 0 (1,1)
result:
ok correct!
Test #2:
score: 0
Accepted
time: 2ms
memory: 5868kb
input:
2 1 .X
output:
0.0000000000 0 (1,1) (2,1)
result:
ok correct!
Test #3:
score: 0
Accepted
time: 0ms
memory: 5876kb
input:
2 1 X.
output:
0.0000000000 0 (1,1) (2,1)
result:
ok correct!
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 5852kb
input:
1 2 . X
output:
0.0000000000 0 (1,2) (1,1)
result:
wrong answer Read (1,2) but expected (1,1)