QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387312#5112. Where Am I?ucup-team1209#WA 0ms3840kbC++202.4kb2024-04-12 12:56:012024-04-12 12:56:02

Judging History

你现在查看的是最新测评结果

  • [2024-04-12 12:56:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3840kb
  • [2024-04-12 12:56:01]
  • 提交

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; 
}

Details

Tip: Click on the bar to expand more detailed information

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