QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91033#5112. Where Am I?vk1cd314WA 2ms3660kbC++202.7kb2023-03-26 19:34:032023-03-26 19:34:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-26 19:34:07]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3660kb
  • [2023-03-26 19:34:03]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m; scanf("%d %d", &n, &m);
    vector <vector <char>> a(n, vector <char>(m));
    for (auto &v : a) for (auto &c : v) scanf(" %c", &c);
    vector <int> dirx, diry;
    vector <pair <int, int>> xs;
    
    int sx = 0, sy = 0;
    bool dir = true;
    dirx.push_back(0), diry.push_back(0);
    for (int i = 0, j = 1; i < 2 * 105; ++i, ++j, dir ^= 1) {
        if (dir) {
            for (int k = 0; k < j; ++k) dirx.push_back(--sx), diry.push_back(sy);
            for (int k = 0; k < j; ++k) dirx.push_back(sx), diry.push_back(++sy);
        } else {
            for (int k = 0; k < j; ++k) dirx.push_back(++sx), diry.push_back(sy);
            for (int k = 0; k < j; ++k) dirx.push_back(sx), diry.push_back(--sy);
        }
    }

    printf("%d\n", dirx.size());

    auto ok = [&](int i, int j) {
        if (!((0 <= i && i < n) && (0 <= j && j < m))) return false;
        return a[i][j] == 'X';
    };

    vector <vector <vector <int>>> pos(n, vector <vector <int>>(m));
    vector <pair <int, int>> all;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            vector <int> go;
            for (int k = 0; k < (int) dirx.size(); ++k) {
                int ni = i + dirx[k], nj = j + diry[k];
                if (ok(ni, nj)) {
                    go.push_back(k);
                }
            }
            pos[i][j] = go;
            all.push_back({i, j});
        }
    }

    sort(all.begin(), all.end(), [&](auto &a, auto &b) {
        return pos[a.first][a.second] < pos[b.first][b.second];
    });

    auto get = [&](int i) {
        if (i == 0 || i == n * m) return 0;
        int match = 0;
        auto [i2, j2] = all[i];
        auto [i1, j1] = all[i - 1];
        while (pos[i1][j1][match] == pos[i2][j2][match]) ++match;
        return min(pos[i1][j1][match], pos[i2][j2][match]);
    };

    int max_ans = -1;
    vector <pair <int, int>> mans;
    long long tot = 0;
    for (int i = 0; i < (int) all.size(); ++i) {
        int add = max(get(i), get(i + 1));
        if (add > max_ans) {
            max_ans = add;
            mans.clear();
            mans.push_back(all[i]);
        } else if (add == max_ans) {
            mans.push_back(all[i]);
        }
        tot += add;
    }

    for (auto &[x, y] : mans) {
        swap(x, y);
        x = x + 1;
        y = n - y;
    }
    sort(mans.begin(), mans.end(), [&](auto &a, auto &b) {
        if (a.second == b.second) return a.second < b.second;
        return a.first < b.first;
    });
    
    printf("%.3lf\n%d\n", (double) tot / (n * m), max_ans);
    for (auto [x, y] : mans) printf("(%d,%d) ", x, y);    
}

详细

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 3660kb

input:

1 1
X

output:

44311
0.000
0
(1,1) 

result:

wrong answer read 44311.000000 but expected 0.000000, error = 44311.000000