General

# Author Problem Lang Verdict Time Memory Sent Judged
65655948 Practice:
Devil
1261C - 14 GNU C++14 Accepted 452 ms 109040 KB 2019-11-24 13:40:57 2019-11-24 13:40:57

→ Source
#include <bits/stdc++.h>

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ld> point;
#define F first
#define S second

int main()
{
#ifdef DGC
freopen("a.in", "r", stdin);
//freopen("b.out", "w", stdout);
#endif

ios_base::sync_with_stdio(0), cin.tie(0);

int n, m;
cin >> n >> m;
vector<string> a(n);
for (auto &i : a) cin >> i;

vector<vector<ll>> sum(n+1, vector<ll>(m+1));

auto get = [&](vector<vector<ll>> &acc, int i, int j, int k, int l)
{
return acc[j][l] - acc[i-1][l] - acc[j][k-1] + acc[i-1][k-1];
};

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (a[i-1][j-1] == 'X');

vector<pair<int, int>> pos;
auto f = [&](int t)
{
vector<vector<ll>> fire(n+2, vector<ll>(m+2));

pos.clear();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (i-t > 0 && i+t <= n && j-t > 0 && j+t <= m && get(sum, i-t, i+t, j-t, j+t) == ((ll)2*t+1)*(2*t+1))
{
pos.push_back({ i, j });
++fire[i-t][j-t];
--fire[i-t][j+t+1];
--fire[i+t+1][j-t];
++fire[i+t+1][j+t+1];
}

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
fire[i][j] += fire[i-1][j] + fire[i][j-1] - fire[i-1][j-1];

for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i-1][j-1] == 'X' && fire[i][j] == 0)
return false;

return true;
};

int lo = 0, hi = min(n, m);
while (lo < hi)
{
int md = (lo + hi + 1) >> 1;
if (f(md))
lo = md;
else
hi = md-1;
}

f(lo);
cout << lo << "\n";
vector<string> ans(n, string(m, '.'));
for (auto i : pos)
ans[i.F-1][i.S-1] = 'X';

for (auto &i : ans)
cout << i << "\n";

return 0;
}


?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?