結果
問題 | No.2641 draw X |
ユーザー | tnakao0123 |
提出日時 | 2024-02-20 21:32:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 124 ms / 2,000 ms |
コード長 | 2,616 bytes |
コンパイル時間 | 717 ms |
コンパイル使用メモリ | 63,952 KB |
実行使用メモリ | 24,832 KB |
最終ジャッジ日時 | 2024-09-29 03:52:41 |
合計ジャッジ時間 | 3,274 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
/* -*- coding: utf-8 -*- * * 2641.cc: No.2641 draw X - yukicoder */ #include<cstdio> #include<vector> #include<algorithm> #include<utility> using namespace std; /* constant */ const int MAX_HW = 1000000; /* typedef */ typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pii; typedef vector<pii> vpii; typedef vector<vpii> vvpii; /* global variables */ char s[MAX_HW + 4], t[MAX_HW + 4]; /* subroutines */ /* main */ int main() { int h, w; scanf("%d%d", &h, &w); int hw = h * w; for (int i = 0; i < h; i++) scanf("%s", s + i * w); if (h < w) { for (int y = 0; y < h; y++) for (int x = 0; x < w; x++) t[x * h + y] = s[y * w + x]; copy(t, t + hw, s); swap(h, w); } int m = h + w - 1; vvpii ps0(m, vpii()), ps1(m, vpii()); for (int i = 0; i < m; i++) { int x0 = max(0, i - (h - 1)), x1 = min(w - 1, i) + 1; // y + x = i -> y = i - x for (int r = x0; r < x1;) { while (r < x1 && s[(i - r) * w + r] == '.') r++; if (r >= x1) break; int l = r; while (r < x1 && s[(i - r) * w + r] == '#') r++; ps0[i].push_back({r - 1, l}); } // (h - 1 - y) + x = i -> y = (h - 1) - (i - x) for (int r = x0; r < x1;) { while (r < x1 && s[(h - 1 - (i - r)) * w + r] == '.') r++; if (r >= x1) break; int l = r; while (r < x1 && s[(h - 1 - (i - r)) * w + r] == '#') r++; ps1[i].push_back({r - 1, l}); } } vvi rs(h, vi(w, 0)); for (int y = 1; y < h - 1; y++) for (int x = 1; x < w - 1; x++) if (s[y * w + x] == '#') { int i0 = y + x, i1 = (h - 1 - y) + x; auto vit0 = lower_bound(ps0[i0].begin(), ps0[i0].end(), pii(x, -1)); auto vit1 = lower_bound(ps1[i1].begin(), ps1[i1].end(), pii(x, -1)); rs[y][x] = min(min(x - vit0->second, vit0->first - x), min(x - vit1->second, vit1->first - x)); } ps0.clear(), ps1.clear(); vvi cs0(m, vi(w + 1, 0)), cs1(m, vi(w + 1, 0)); for (int y = 1; y < h - 1; y++) for (int x = 1; x < w - 1; x++) if (rs[y][x]) { int r = rs[y][x]; int i0 = y + x, i1 = (h - 1 - y) + x; cs0[i0][x - r]++, cs0[i0][x + r + 1]--; cs1[i1][x - r]++, cs1[i1][x + r + 1]--; } fill(t, t + hw, '.'); for (int i = 0; i < m; i++) { for (int x = 0; x < w; x++) { if (cs0[i][x] > 0) t[(i - x) * w + x] = '#'; cs0[i][x + 1] += cs0[i][x]; } for (int x = 0; x < w; x++) { if (cs1[i][x] > 0) t[(h - 1 - (i - x)) * w + x] = '#'; cs1[i][x + 1] += cs1[i][x]; } } for (int i = 0; i < hw; i++) if (s[i] != t[i]) { puts("No"); return 0; } puts("Yes"); return 0; }