QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#91036#5112. Where Am I?vk1cd314RE 212ms5416kbC++202.7kb2023-03-26 19:41:262023-03-26 19:41:29

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:41:29]
  • 评测
  • 测评结果:RE
  • 用时:212ms
  • 内存:5416kb
  • [2023-03-26 19:41:26]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m; scanf("%d %d", &m, &n);
    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 < 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);
        }
    }

    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: 100
Accepted
time: 2ms
memory: 3588kb

input:

1 1
X

output:

0.000
0
(1,1) 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

2 1
.X

output:

0.000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

score: 0
Accepted
time: 2ms
memory: 3692kb

input:

2 1
X.

output:

0.000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

1 2
.
X

output:

0.000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

score: 0
Accepted
time: 2ms
memory: 3768kb

input:

1 2
X
.

output:

0.000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

score: 0
Accepted
time: 2ms
memory: 3696kb

input:

2 1
XX

output:

3.000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

3 3
XXX
X.X
XXX

output:

3.111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 212ms
memory: 5416kb

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:

4757.947
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: -100
Runtime Error

input:

100 100
X...................................................................................................
....................................................................................................
.............................................................................................

output:


result: