結果
| 問題 |
No.2641 draw X
|
| コンテスト | |
| ユーザー |
 LyricalMaestro
|
| 提出日時 | 2025-06-29 02:24:04 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,569 bytes |
| コンパイル時間 | 369 ms |
| コンパイル使用メモリ | 82,220 KB |
| 実行使用メモリ | 289,440 KB |
| 最終ジャッジ日時 | 2025-06-29 02:24:11 |
| 合計ジャッジ時間 | 6,269 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | AC * 16 TLE * 1 -- * 24 |
ソースコード
def main():
H, W = map(int, input().split())
S = []
for _ in range(H):
S.append(input())
# #の累積を取る
i_j1 = {}
i_j2 = {}
for i in range(H):
for j in range(W):
x = i + j
y = i - j
if x not in i_j1:
i_j1[x] = []
i_j1[x].append(i)
if y not in i_j2:
i_j2[y] = []
i_j2[y].append(i)
i_j1_cums = {}
for key, values in i_j1.items():
values.sort()
new_values = []
c = 0
for i in values:
j = key - i
if S[i][j] == "#":
c += 1
new_values.append(c)
value_map = {}
for i in range(len(values)):
v = new_values[i]
k = values[i]
value_map[k] = v
i_j1_cums[key] = value_map
i_j2_cums = {}
for key, values in i_j2.items():
values.sort()
new_values = []
c = 0
for i in values:
j = i - key
if S[i][j] == "#":
c += 1
new_values.append(c)
value_map = {}
for i in range(len(values)):
v = new_values[i]
k = values[i]
value_map[k] = v
i_j2_cums[key] = value_map
i_j1_imos= {}
i_j2_imos= {}
for i in range(H):
for j in range(W):
if S[i][j] == "#":
is_ok = True
for di, dj in ((1, 1), (1, -1), (-1, 1), (- 1, -1)):
new_i = di + i
new_j = dj + j
if not (0 <= new_i < H and 0 <= new_j < W):
is_ok = False
break
if S[new_i][new_j] == ".":
is_ok = False
break
if not is_ok:
continue
# i_j1
def solve(ar, i, mid):
high_i = i + mid
low_i = i - mid
if high_i not in ar:
return False
if low_i not in ar:
return False
if (low_i - 1) not in ar:
x = ar[high_i]
return x == 1 + 2 * mid
else:
x = ar[high_i]
x1 = ar[low_i - 1]
return (x - x1) == 1 + 2 * mid
key = i + j
ar = i_j1_cums[key]
low = 1
high = max(H, W)
while high - low > 1:
mid = (high + low) // 2
if solve(ar, i, mid):
low = mid
else:
high = mid
if solve(ar, i, high):
ij1_val = high
else:
ij1_val = low
key = i - j
ar = i_j2_cums[key]
low = 1
high = max(H, W)
while high - low > 1:
mid = (high + low) // 2
if solve(ar, i, mid):
low = mid
else:
high = mid
if solve(ar, i, high):
ij2_val = high
else:
ij2_val = low
ans = min(ij1_val, ij2_val)
key = i + j
if key not in i_j1_imos:
i_j1_imos[key] = {}
min_i = i - ans
max_i = i + ans + 1
if min_i not in i_j1_imos[key]:
i_j1_imos[key][min_i] = 0
i_j1_imos[key][min_i] += 1
if max_i not in i_j1_imos[key]:
i_j1_imos[key][max_i] = 0
i_j1_imos[key][max_i] -= 1
key = i - j
if key not in i_j2_imos:
i_j2_imos[key] = {}
min_i = i - ans
max_i = i + ans + 1
if min_i not in i_j2_imos[key]:
i_j2_imos[key][min_i] = 0
i_j2_imos[key][min_i] += 1
if max_i not in i_j2_imos[key]:
i_j2_imos[key][max_i] = 0
i_j2_imos[key][max_i] -= 1
passed = [[0] * W for _ in range(H)]
for key, values_map in i_j1_imos.items():
min_i = min(values_map.keys())
max_i = max(values_map.keys())
c = 0
for i in range(max_i - min_i):
i0 = min_i + i
if i0 in values_map:
c += values_map[i0]
j0 = key - i0
passed[i0][j0] += c
for key, values_map in i_j2_imos.items():
min_i = min(values_map.keys())
max_i = max(values_map.keys())
c = 0
for i in range(max_i - min_i):
i0 = min_i + i
if i0 in values_map:
c += values_map[i0]
j0 = i0 - key
passed[i0][j0] += c
is_ok = True
for i in range(H):
for j in range(W):
if passed[i][j] > 0 and S[i][j] == ".":
is_ok = False
elif passed[i][j] == 0 and S[i][j] == "#":
is_ok = False
if is_ok:
print("Yes")
else:
print("No")
if __name__ == "__main__":
main()