結果
問題 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,816 KB |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,816 KB |
testcase_09 | AC | 2 ms
6,816 KB |
testcase_10 | AC | 2 ms
6,820 KB |
testcase_11 | AC | 2 ms
6,816 KB |
testcase_12 | AC | 2 ms
6,820 KB |
testcase_13 | AC | 2 ms
6,820 KB |
testcase_14 | AC | 2 ms
6,816 KB |
testcase_15 | AC | 31 ms
24,704 KB |
testcase_16 | AC | 70 ms
24,832 KB |
testcase_17 | AC | 2 ms
6,820 KB |
testcase_18 | AC | 2 ms
6,816 KB |
testcase_19 | AC | 1 ms
6,820 KB |
testcase_20 | AC | 8 ms
6,816 KB |
testcase_21 | AC | 14 ms
6,816 KB |
testcase_22 | AC | 8 ms
6,820 KB |
testcase_23 | AC | 11 ms
6,816 KB |
testcase_24 | AC | 3 ms
6,820 KB |
testcase_25 | AC | 4 ms
6,820 KB |
testcase_26 | AC | 19 ms
6,820 KB |
testcase_27 | AC | 5 ms
6,816 KB |
testcase_28 | AC | 25 ms
11,648 KB |
testcase_29 | AC | 28 ms
15,872 KB |
testcase_30 | AC | 32 ms
13,440 KB |
testcase_31 | AC | 33 ms
10,752 KB |
testcase_32 | AC | 46 ms
16,256 KB |
testcase_33 | AC | 51 ms
16,512 KB |
testcase_34 | AC | 40 ms
14,080 KB |
testcase_35 | AC | 35 ms
10,112 KB |
testcase_36 | AC | 72 ms
22,144 KB |
testcase_37 | AC | 124 ms
23,296 KB |
testcase_38 | AC | 87 ms
21,376 KB |
testcase_39 | AC | 94 ms
24,320 KB |
testcase_40 | AC | 120 ms
23,424 KB |
testcase_41 | AC | 59 ms
21,376 KB |
testcase_42 | AC | 103 ms
21,760 KB |
testcase_43 | AC | 97 ms
21,888 KB |
ソースコード
/* -*- 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; }