QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#387312 | #5112. Where Am I? | ucup-team1209# | WA | 0ms | 3840kb | C++20 | 2.4kb | 2024-04-12 12:56:01 | 2024-04-12 12:56:02 |
Judging History
answer
#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using ll = long long ;
using pi = pair <int, int> ;
cs int N = 105 + 5;
void cmx(ll & x, ll y) {
if(x < y) x = y;
}
int n, m;
char mp[N][N];
int ans[N][N];
int Map(int x, int y) {
if(x <= 0 || y <= 0 || x > n || y > m) return 0;
return mp[x][y] == 'X';
}
pi direction(int d) {
if(d == 0) return {-1, 0};
int m = sqrt(d);
if(m % 2 == 0) -- m;
if(d < m * m + m) {
return {0, 1};
}
if(d < (m + 1) * (m + 1)) {
return {1, 0};
}
if(d < (m + 1) * (m + 2)) {
return {0, -1};
}
return {-1, 0};
}
void dfs(vector <pi> & S, int d, int dx, int dy) {
if(S.empty()) return;
if(S.size() == 1) {
auto [x, y] = S[0];
ans[x - dx][y - dy] = d - 1;
return;
}
vector <pi> T[2];
auto [cx, cy] = direction(d);
for(auto [x, y] : S) {
// cout << x << ' ' << y << ' ' << Map(x, y) << endl;
T[Map(x, y)].pb({x + cx, y + cy});
}
// cout << d << ' ' << dx <<' ' << dy << endl;
// for(auto [x, y] :S) cout << x << ' ' << y <<' '; cout << endl;
// static int t = 0;
// if(++ t == 50) exit(0);
dfs(T[0], d + 1, dx + cx, dy + cy);
dfs(T[1], d + 1, dx + cx, dy + cy);
}
int main() {
#ifdef zqj
freopen("1.in","r",stdin);
#endif
// ios :: sync_with_stdio(0), cin.tie(0);
cin >> m >> n;
vector <pi> S;
for(int i = 1; i <= n; i++) {
scanf("%s", mp[i] + 1);
for(int j = 1; j <= m; j++) {
S.pb({i, j});
}
}
dfs(S, 0, 0, 0);
int sum = 0, mx = 0;
vector <pi> t;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
sum += ans[i][j];
if(ans[i][j] > mx) {
t = {{n - i + 1, j}};
mx = ans[i][j];
}
else if(ans[i][j] == mx) {
t.pb({n - i + 1, j});
}
}
}
// cout << "FFFFF " << sum << ' ' << mx << endl;
sort(t.begin(), t.end());
printf("%.10lf\n", 1.0 * sum / (n * m));
cout << mx << '\n';
for(int i = 0; i < t.size(); i++) {
auto [x, y] = t[i];
cout << "(" << y << "," << x << ")";
if(i + 1 < t.size()) cout << ' ';
}
cout << '\n';
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3840kb
input:
1 1 X
output:
-1.0000000000 0
result:
wrong answer read -1.000000 but expected 0.000000, error = 1.000000