結果
問題 | No.2641 draw X |
ユーザー |
![]() |
提出日時 | 2024-02-19 21:39:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 5,499 bytes |
コンパイル時間 | 2,253 ms |
コンパイル使用メモリ | 207,684 KB |
最終ジャッジ日時 | 2025-02-19 16:46:06 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#ifndef LOCAL#define FAST_IO#endif// ============#include <bits/stdc++.h>#define OVERRIDE(a, b, c, d, ...) d#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)#define PER3(i, m, n) for (i32 i = (i32)(n)-1; i >= (i32)(m); --i)#define PER(...) OVERRIDE(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)#define ALL(x) begin(x), end(x)#define LEN(x) (i32)(x.size())using namespace std;using u32 = unsigned int;using u64 = unsigned long long;using i32 = signed int;using i64 = signed long long;using f64 = double;using f80 = long double;using pi = pair<i32, i32>;using pl = pair<i64, i64>;template <typename T>using V = vector<T>;template <typename T>using VV = V<V<T>>;template <typename T>using VVV = V<V<V<T>>>;template <typename T>using VVVV = V<V<V<V<T>>>>;template <typename T>using PQR = priority_queue<T, V<T>, greater<T>>;template <typename T>bool chmin(T &x, const T &y) {if (x > y) {x = y;return true;}return false;}template <typename T>bool chmax(T &x, const T &y) {if (x < y) {x = y;return true;}return false;}template <typename T>i32 lob(const V<T> &arr, const T &v) {return (i32)(lower_bound(ALL(arr), v) - arr.begin());}template <typename T>i32 upb(const V<T> &arr, const T &v) {return (i32)(upper_bound(ALL(arr), v) - arr.begin());}template <typename T>V<i32> argsort(const V<T> &arr) {V<i32> ret(arr.size());iota(ALL(ret), 0);sort(ALL(ret), [&](i32 i, i32 j) -> bool {if (arr[i] == arr[j]) {return i < j;} else {return arr[i] < arr[j];}});return ret;}#ifdef INT128using u128 = __uint128_t;using i128 = __int128_t;#endif[[maybe_unused]] constexpr i32 INF = 1000000100;[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;struct SetUpIO {SetUpIO() {#ifdef FAST_IOios::sync_with_stdio(false);cin.tie(nullptr);#endifcout << fixed << setprecision(15);}} set_up_io;void scan(char &x) { cin >> x; }void scan(u32 &x) { cin >> x; }void scan(u64 &x) { cin >> x; }void scan(i32 &x) { cin >> x; }void scan(i64 &x) { cin >> x; }void scan(string &x) { cin >> x; }template <typename T>void scan(V<T> &x) {for (T &ele : x) {scan(ele);}}void read() {}template <typename Head, typename... Tail>void read(Head &head, Tail &...tail) {scan(head);read(tail...);}#define CHAR(...) \char __VA_ARGS__; \read(__VA_ARGS__);#define U32(...) \u32 __VA_ARGS__; \read(__VA_ARGS__);#define U64(...) \u64 __VA_ARGS__; \read(__VA_ARGS__);#define I32(...) \i32 __VA_ARGS__; \read(__VA_ARGS__);#define I64(...) \i64 __VA_ARGS__; \read(__VA_ARGS__);#define STR(...) \string __VA_ARGS__; \read(__VA_ARGS__);#define VEC(type, name, size) \V<type> name(size); \read(name);#define VVEC(type, name, size1, size2) \VV<type> name(size1, V<type>(size2)); \read(name);// ============#ifdef DEBUGF#else#define DBG(...) (void)0#endifvoid solve() {I32(h, w);VEC(string, s, h);i32 dx[] = {1, 1, -1, -1}, dy[] = {1, -1, 1, -1};VVV<i32> cnt(4, VV<i32>(h, V<i32>(w, 0)));PER(i, h) PER(j, w) {if (s[i][j] == '#') {if (i + 1 < h && j + 1 < w) {cnt[0][i][j] = cnt[0][i + 1][j + 1] + 1;} else {cnt[0][i][j] = 1;}}}PER(i, h) REP(j, w) {if (s[i][j] == '#') {if (i + 1 < h && j - 1 >= 0) {cnt[1][i][j] = cnt[1][i + 1][j - 1] + 1;} else {cnt[1][i][j] = 1;}}}REP(i, h) PER(j, w) {if (s[i][j] == '#') {if (i - 1 >= 0 && j + 1 < w) {cnt[2][i][j] = cnt[2][i - 1][j + 1] + 1;} else {cnt[2][i][j] = 1;}}}REP(i, h) REP(j, w) {if (s[i][j] == '#') {if (i - 1 >= 0 && j - 1 >= 0) {cnt[3][i][j] = cnt[3][i - 1][j - 1] + 1;} else {cnt[3][i][j] = 1;}}}VVV<i32> draw(4, VV<i32>(h, V<i32>(w, 0)));REP(i, h) REP(j, w) {i32 k = INF;REP(aaa, 4) {chmin(k, cnt[aaa][i][j]);}if (k >= 2) {REP(aaa, 4) {chmax(draw[aaa][i][j], k);}DBG(i, j, k);}}REP(i, h - 1) REP(j, w - 1) {chmax(draw[0][i + 1][j + 1], draw[0][i][j] - 1);}REP(i, h - 1) PER(j, 1, w) {chmax(draw[1][i + 1][j - 1], draw[1][i][j] - 1);}PER(i, 1, h) REP(j, w - 1) {chmax(draw[2][i - 1][j + 1], draw[2][i][j] - 1);}PER(i, 1, h) PER(j, 1, w) {chmax(draw[3][i - 1][j - 1], draw[3][i][j] - 1);}REP(i, h) REP(j, w) {if (s[i][j] == '#') {i32 k = 0;REP(aaa, 4) {chmax(k, draw[aaa][i][j]);}if (k == 0) {cout << "No\n";return;}}}cout << "Yes\n";}int main() {i32 t = 1;// cin >> t;while (t--) {solve();}}