結果
問題 |
No.678 2Dシューティングゲームの必殺ビーム
|
ユーザー |
![]() |
提出日時 | 2025-04-09 21:03:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 2,534 bytes |
コンパイル時間 | 809 ms |
コンパイル使用メモリ | 82,456 KB |
実行使用メモリ | 64,840 KB |
最終ジャッジ日時 | 2025-04-09 21:05:45 |
合計ジャッジ時間 | 1,582 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
def main(): import sys input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr +=1 xLB = int(input[ptr]) ptr +=1 xRB = int(input[ptr]) ptr +=1 enemies = [] for i in range(N): XL = int(input[ptr]) ptr +=1 YU = int(input[ptr]) ptr +=1 XR = int(input[ptr]) ptr +=1 YD = int(input[ptr]) ptr +=1 enemies.append( (YD, XL, XR, i) ) # Store YD for sorting, XL, XR, index # Sort enemies by YD descending, then by whatever enemies.sort(reverse=True, key=lambda x: (x[0], x[3])) result = [0]*N intervals = [] # list of (start, end), kept sorted and non-overlapping for yd, xl, xr, index in enemies: # Compute intersection with beam's x range beam_start = xLB beam_end = xRB start = max(beam_start, xl) end = min(beam_end, xr) if start > end: result[index] = 0 continue # Compute the difference between [start, end] and intervals delta = [ (start, end) ] for (s, e) in intervals: new_delta = [] for d in delta: ds, de = d if de < s: new_delta.append( (ds, de) ) elif ds > e: new_delta.append( (ds, de) ) else: if ds < s: new_delta.append( (ds, s-1) ) if de > e: new_delta.append( (e+1, de) ) delta = new_delta if delta: result[index] = 1 # Merge the new intervals into the existing intervals temp_intervals = intervals + delta temp_intervals.sort() merged = [] for interval in temp_intervals: if not merged: merged.append( interval ) else: last_start, last_end = merged[-1] current_start, current_end = interval if current_start <= last_end + 1: # Overlapping or adjacent, merge merged[-1] = ( min(last_start, current_start), max(last_end, current_end) ) else: merged.append( interval ) intervals = merged else: result[index] = 0 # Output in original order for i in range(N): print(result[i]) if __name__ == "__main__": main()