結果
問題 |
No.1242 高橋君とすごろく
|
ユーザー |
![]() |
提出日時 | 2025-04-09 21:02:53 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,228 bytes |
コンパイル時間 | 377 ms |
コンパイル使用メモリ | 82,364 KB |
実行使用メモリ | 148,616 KB |
最終ジャッジ日時 | 2025-04-09 21:04:22 |
合計ジャッジ時間 | 4,213 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 6 TLE * 1 -- * 17 |
ソースコード
def main(): import sys from bisect import bisect_left def merge_intervals(intervals): if not intervals: return [] intervals.sort() merged = [intervals[0].copy()] for current in intervals[1:]: last = merged[-1] if current[0] <= last[1] + 1: last[1] = max(last[1], current[1]) else: merged.append(current.copy()) return merged def subtract_points_from_interval(interval, points): start, end = interval points = sorted(points) res = [] current_start = start for p in points: if p < current_start: continue if current_start < p: res.append([current_start, p - 1]) current_start = p + 1 if current_start <= end: res.append([current_start, end]) return res def interval_intersection(a, b): res = [] i = j = 0 len_a = len(a) len_b = len(b) while i < len_a and j < len_b: a_start, a_end = a[i] b_start, b_end = b[j] start = max(a_start, b_start) end = min(a_end, b_end) if start <= end: res.append([start, end]) if a_end < b_end: i += 1 else: j += 1 return merge_intervals(res) N, K = map(int, sys.stdin.readline().split()) A = list(map(int, sys.stdin.readline().split())) game_over = set(A) A_sorted = sorted(A) current_intervals = [[N, N]] visited = set() while True: tuple_intervals = tuple(tuple(interval) for interval in current_intervals) if tuple_intervals in visited: break visited.add(tuple_intervals) new_intervals = None for x in range(1, 7): x_ranges = [] choices = [x, 7 - x] for choice in choices: part1 = [] lower = N - choice s_lower = max(lower, 1) s_upper = N - 1 if s_lower <= s_upper: part1 = [[s_lower, s_upper]] part2 = [] for interval in current_intervals: L, R = interval s_start = L - choice s_end = R - choice if s_end < 1: continue s_start = max(s_start, 1) if s_start > s_end: continue current_range = [s_start, s_end] points_to_exclude = [] for a in A_sorted: if a >= N: continue s_val = a - choice if s_start <= s_val <= s_end: points_to_exclude.append(s_val) subtracted = subtract_points_from_interval(current_range, points_to_exclude) part2.extend(subtracted) merged_part = merge_intervals(part1 + part2) x_ranges.extend(merged_part) x_possible = merge_intervals(x_ranges) if not x_possible: new_intervals = [] break if new_intervals is None: new_intervals = x_possible else: new_intervals = interval_intersection(new_intervals, x_possible) if not new_intervals: break if new_intervals is None: new_intervals = [] new_intervals = merge_intervals(new_intervals) if not new_intervals: break new_tuple = tuple(tuple(interval) for interval in new_intervals) if new_tuple == tuple_intervals: break current_intervals = new_intervals for interval in current_intervals: if interval[0] <= 1 <= interval[1]: print("Yes") return has = any(interval[0] <= 1 <= interval[1] for interval in current_intervals) print("Yes" if has else "No") if __name__ == "__main__": main()