QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#385476 | #5108. Prehistoric Programs | SolitaryDream# | RE | 0ms | 0kb | C++17 | 2.2kb | 2024-04-10 19:47:28 | 2024-04-10 19:47:29 |
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