QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356537#5112. Where Am I?TWTP_TCTF#WA 0ms4196kbC++172.8kb2024-03-17 22:37:022024-03-17 22:37:03

Judging History

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

  • [2024-03-17 22:37:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4196kb
  • [2024-03-17 22:37:02]
  • 提交

answer

#include <bits/stdc++.h>

#define IO  ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL);
#define ll long long
#define ld long double
using namespace std;
const int N = 1e4 + 5, C = 5e4 + 7;
int mod = 998244353;
vector<int> dist[N];
int ans[N];
int n, m;
string s[105];

pair<int, int> getindex(int flat) {
    return {flat / m, flat % m};
}

int flatten(int i, int j) {
    return i * m + j;
}

int getdist(int a, int b, int x, int y) {
    x -= a;
    y -= b;
    if (x == 0 && y == 0)return 0;
    int p = max(abs(x), abs(y)) - 1;
    int d = (2 * p + 1) * (2 * p + 1) - 1;
    if (x == -p - 1 && y >= -p) {
        return d + 1 + y - (-p);
    }
    d += 1 + 2 * p + 1;
    if (y == p + 1) {
        return d + x - (-p - 1);
    }
    d += 2 * p + 2;
    if (x == p + 1) {
        return d + p + 1 - y;
    }
    d += 2 * p + 2;
    return d + p + 1 - x;
}

void pre() {
    vector<pair<int, int>> xs;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (s[i][j] == 'X')
                xs.push_back({i, j});

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            for (auto it: xs)
                dist[flatten(i, j)].push_back(getdist(i, j, it.first, it.second));

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            sort(dist[flatten(i, j)].rbegin(), dist[flatten(i, j)].rend());
}

void solve(vector<int> &indexs, bool del = 1) {
    map<int, vector<int>> mp;
    int mx1 = 0, mx2;
    for (int i: indexs) {
        if (del)
            dist[i].pop_back();
        if (dist[i].back() >= mx1) {
            mx2 = mx1;
            mx1 = dist[i].back();

        } else if (dist[i].back() > mx2)
            mx2 = dist[i].back();
        mp[dist[i].back()].push_back(i);
    }
    for (auto it: mp) {
        if (it.second.size() == 1)
            ans[it.second[0]] = min(mx2, it.first);
        else
            solve(it.second);
    }

}

ld calExp() {
    ll total = 0;
    for (int i = 0; i < n * m; ++i)
        total += ans[i];
    return (ld) total / (n * m);
}

int main() {
    IO
    cin >> m >> n;
    for (int i = 0; i < n; ++i)
        cin >> s[i];

    pre();
    vector<int> index;
    for (int i = 0; i < n * m; ++i)
        index.push_back(i);
    solve(index, 0);
    cout << fixed << setprecision(3) << calExp() << '\n';
    int mx = 0;
    for (int i = 0; i < n * m; ++i)
        mx = max(mx, ans[i]);
    cout << mx << '\n';
    vector<pair<int, int>> tmp;
    for (int i = 0; i < n * m; ++i) {
        if (ans[i] == mx) {
            auto p = getindex(i);
            tmp.push_back({n - p.first, p.second + 1});
        }

    }
    std::sort(tmp.begin(), tmp.end());
    for (auto p: tmp) {

        cout << "(" << p.second << ", " << p.first << ") ";

    }


}



详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4196kb

input:

1 1
X

output:

0.000
0
(1, 1) 

result:

wrong answer Read (1, but expected (1,1)