def solution(yourBalloonNames, operations): import heapq MAX_ALT = 1 << 15 # 32768, valid altitudes: 1..32767 SAFE_LIMIT = 15.0 REGAIN_SECONDS = 300 EPS = 1e-9 your_set = set(yourBalloonNames) # Precompute kernel for distance d in [-32767, 32767] # kernel(d) = 1 / (1 + (d/100)^2) offset = MAX_ALT - 1 kernel = [0.0] * (2 * (MAX_ALT - 1) + 1) for d in range(-(MAX_ALT - 1), (MAX_ALT - 1) + 1): x = d / 100.0 kernel[d + offset] = 1.0 / (1.0 + x * x) # Wind field computed at every integer altitude. wind_field = [0.0] * MAX_ALT safe_flag = [True] * MAX_ALT # True iff wind_field[h] <= 15 wind_sources = {} # center_altitude -> windSpeedAtAltitude class Balloon: __slots__ = ("is_yours", "airborne", "alt", "stable", "safe_start", "ver") def __init__(self, is_yours): self.is_yours = is_yours self.airborne = False self.alt = 0 self.stable = True self.safe_start = None self.ver = 0 balloons = {} # name -> Balloon alt_to_balloons = {} # altitude -> set(names) for airborne balloons at that exact altitude # Heap of scheduled regain-stability events: (due_time, name, ver_at_schedule) regain_heap = [] # Heap to track highest stable competitor: (-alt, name, ver_at_push) comp_heap = [] current_time = float("-inf") def get_balloon(name): b = balloons.get(name) if b is None: b = Balloon(is_yours=(name in your_set)) balloons[name] = b return b def remove_from_alt(name, alt): s = alt_to_balloons.get(alt) if not s: return s.discard(name) if not s: alt_to_balloons.pop(alt, None) def add_to_alt(name, alt): s = alt_to_balloons.get(alt) if s is None: s = set() alt_to_balloons[alt] = s s.add(name) def mark_unstable(b, ts): # Only do work if it changes something relevant if b.stable or b.safe_start is not None: b.ver += 1 b.stable = False b.safe_start = None def start_safe_timer_if_needed(b, ts, name): # Called when altitude becomes safe while balloon is unstable. if not b.stable and b.safe_start is None: b.ver += 1 b.safe_start = ts heapq.heappush(regain_heap, (ts + REGAIN_SECONDS, name, b.ver)) def advance_time(ts): nonlocal current_time # Process any stability regains due at/before ts. while regain_heap and regain_heap[0][0] <= ts: due, name, ver = heapq.heappop(regain_heap) b = balloons.get(name) if b is None or not b.airborne: continue if b.ver != ver: continue if b.stable: continue if b.alt <= 0 or b.alt >= MAX_ALT: continue # Must still be in safe wind at the due time. if safe_flag[b.alt]: b.ver += 1 b.stable = True b.safe_start = None if not b.is_yours: heapq.heappush(comp_heap, (-b.alt, name, b.ver)) current_time = ts def current_max_stable_competitor_alt(): while comp_heap: neg_alt, name, ver = comp_heap[0] alt = -neg_alt b = balloons.get(name) if ( b is not None and b.airborne and (not b.is_yours) and b.stable and b.ver == ver and b.alt == alt ): return alt heapq.heappop(comp_heap) return None def set_wind(ts, center_alt, speed): # Validate if not isinstance(center_alt, int) or not (1 <= center_alt < MAX_ALT): return False if not (isinstance(speed, int) or isinstance(speed, float)): return False if speed < 0 or speed >= (1 << 5): return False old = wind_sources.get(center_alt, 0.0) new = float(speed) if abs(new - old) < 1e-15: # No change wind_sources[center_alt] = new return True wind_sources[center_alt] = new delta = new - old # Update wind at all altitudes and handle safe/unsafe flips. for h in range(1, MAX_ALT): wind_field[h] += delta * kernel[h - center_alt + offset] new_safe = wind_field[h] <= (SAFE_LIMIT + EPS) if new_safe != safe_flag[h]: safe_flag[h] = new_safe names = alt_to_balloons.get(h) if names: # Copy to avoid issues if someone modifies sets elsewhere (we don't here, but safe). for nm in tuple(names): b = balloons.get(nm) if b is None or not b.airborne or b.alt != h: continue if not new_safe: mark_unstable(b, ts) else: start_safe_timer_if_needed(b, ts, nm) return True out = [] # Initialize time at 0 if there are ops; otherwise return empty output if not operations: return out current_time = float("-inf") for op in operations: if not op: out.append(False) continue kind = op[0] # Extract timestamp safely try: ts = op[1] except Exception: # Malformed operation out.append([] if kind == "InspectBalloons" else False) continue # Invalid timestamp ordering => no effect if ts < current_time: out.append([] if kind == "InspectBalloons" else False) continue advance_time(ts) if kind == "BalloonAscended": if len(op) != 4: out.append(False) continue _, _, name, alt = op if not isinstance(alt, int) or not (1 <= alt < MAX_ALT): out.append(False) continue b = get_balloon(name) if b.airborne: out.append(False) continue b.ver += 1 b.airborne = True b.alt = alt b.safe_start = None add_to_alt(name, alt) if safe_flag[alt]: b.stable = True if not b.is_yours: heapq.heappush(comp_heap, (-alt, name, b.ver)) else: b.stable = False # safe_start remains None until wind becomes safe out.append(True) elif kind == "BalloonDescended": if len(op) != 3: out.append(False) continue _, _, name = op b = balloons.get(name) if b is None or not b.airborne: out.append(False) continue remove_from_alt(name, b.alt) b.ver += 1 b.airborne = False b.alt = 0 b.stable = True b.safe_start = None out.append(True) elif kind == "SetWindSpeed": if len(op) != 4: out.append(False) continue _, _, center_alt, speed = op out.append(set_wind(ts, center_alt, speed)) elif kind == "InspectBalloons": # Ensure due regain events are already processed via advance_time max_comp = current_max_stable_competitor_alt() threshold = max_comp if max_comp is not None else float("-inf") res = [] for name, b in balloons.items(): if b.is_yours and b.airborne and b.stable and b.alt >= threshold: res.append(name) res.sort() out.append(res) else: # Unknown operation out.append([] if kind == "InspectBalloons" else False) return out