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
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details