QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#385476#5108. Prehistoric ProgramsSolitaryDream#RE 0ms0kbC++172.2kb2024-04-10 19:47:282024-04-10 19:47:29

Judging History

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

  • [2024-04-10 19:47:29]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-10 19:47:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 105;
int dx, dy;
int mp[N][N];
inline int Sqr(int x) {
    return x * x;
}
inline int Dis(int x, int y, int i, int j) {
    if (x == i && y == j) return 0;
    int d1 = max(abs(x - i), (y - j));
    int area = Sqr(2 * d1 - 1); 
    if (x != i - d1 && y == j + d1) return area + (x - (i - d1 + 1));
    if (x == i + d1) return area + d1 * 2 + ((j + d1 - 1) - y);
    if (y == j - d1) return area + d1 * 4 + ((i + d1 - 1) - x);
    if (x == i - d1) return area + d1 * 6 + (y - (j - d1 + 1));
    assert(0);  
}
inline int Calc(const vector<int> &a, const vector<int> &b) {
    int i = 0;
    while (a[i] == b[i]) ++i;
    return min(a[i], b[i]);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> dx >> dy;
    vector<pii> mark;
    
    for (int j = dy; j; --j) {
        static string str;
        cin >> str;
        for (int i = 1; i <= dx; ++i) {
            mp[i][j] = str[i - 1];
            if (mp[i][j] == 'X') mark.push_back({i, j}); 
        }
    }
    vector<pair<vector<int>, pii>> lst; 
    for (int i = 1; i <= dx; ++i)
        for (int j = 1; j <= dy; ++j) {
            vector<int> hs;
            for (auto [x, y] : mark) hs.push_back(Dis(x, y, i, j));
            sort(hs.begin(), hs.end());
            lst.push_back({hs, pii(i, j)});
        }
    sort(lst.begin(), lst.end());
    vector<tuple<int, int, int>> ans;
    int sm = 0;
    for (int i = 0; i < lst.size(); ++i) {
        int lcp = 0;
        if (i) lcp = max(lcp, Calc(lst[i].first, lst[i - 1].first));
        if (i + 1 < lst.size()) lcp = max(lcp, Calc(lst[i].first, lst[i + 1].first));
        auto [x, y] = lst[i].second;
        ans.push_back({lcp, y, x});
        sm += lcp;
    }
    sort(ans.begin(), ans.end());
    cout << double(sm) / lst.size() << endl;
    auto [rst, _y, _x] = ans.back();
    cout << rst << endl;
    auto it = lower_bound(ans.begin(), ans.end(), tuple<int, int, int>{rst, 0, 0});
    for (; it != ans.end(); ++it) {
        auto [_rst, y, x] = *it;
        cout << '(' << x << ',' << y << ')' << ' ';
    }
    cout << endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

50000
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:

-nan

result: