結果
| 問題 | No.2731 Two Colors |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-12 12:26:41 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 765 ms / 3,000 ms |
| + 426µs | |
| コード長 | 2,070 bytes |
| 記録 | |
| コンパイル時間 | 1,725 ms |
| コンパイル使用メモリ | 64,100 KB |
| 実行使用メモリ | 90,604 KB |
| 最終ジャッジ日時 | 2026-11-12 12:27:02 |
| 合計ジャッジ時間 | 18,543 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge1_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 35 |
ソースコード
import sys
import heapq
def main():
input = sys.stdin.buffer.readline
h, w = map(int, input().split())
a = []
for _ in range(h):
a.extend(map(int, input().split()))
n = h * w
shift = (n - 1).bit_length()
mask = (1 << shift) - 1
# bit 0,1: 各色のヒープに追加済み
# bit 2,3: 各色で塗られている
state = bytearray(n)
state[0] = 5
state[n - 1] = 10
p0, p1 = 1, w
p2, p3 = n - w - 1, n - 2
state[p0] |= 1
state[p1] |= 1
state[p2] |= 2
state[p3] |= 2
heaps = [
[(a[p0] << shift) | p0, (a[p1] << shift) | p1],
[(a[p2] << shift) | p2, (a[p3] << shift) | p3]
]
for heap in heaps:
heapq.heapify(heap)
push = heapq.heappush
pop = heapq.heappop
for i in range(n):
side = i & 1
seen = 1 << side
mine = 4 << side
other = 8 >> side
heap = heaps[side]
p = pop(heap) & mask
state[p] |= mine
x, y = divmod(p, w)
if x > 0:
q = p - w
s = state[q]
if s & other:
print(i + 1)
return
if not (s & seen):
state[q] = s | seen
push(heap, (a[q] << shift) | q)
if x + 1 < h:
q = p + w
s = state[q]
if s & other:
print(i + 1)
return
if not (s & seen):
state[q] = s | seen
push(heap, (a[q] << shift) | q)
if y > 0:
q = p - 1
s = state[q]
if s & other:
print(i + 1)
return
if not (s & seen):
state[q] = s | seen
push(heap, (a[q] << shift) | q)
if y + 1 < w:
q = p + 1
s = state[q]
if s & other:
print(i + 1)
return
if not (s & seen):
state[q] = s | seen
push(heap, (a[q] << shift) | q)
main()