Horse Racing-Inter-Uni Programming Contest

Description:

https://interunia.unswcpmsoc.com/task/Horse%20Racing/

Thinking:

Preprocessing Horse Information:

Combine horse information into a list of tuples, horses, where each tuple contains the horse index, starting position, and velocity.
Sort the horses by starting position in descending order. If two horses have the same starting position, sort them by velocity in descending order. This is because the horse with the highest starting position leads initially.

Constructing the Leading Horse Timeline:

• Use a stack stack to maintain the horses that could become the leader.
• For each horse, check if it has the potential to overtake the current leading horse.
  • If the current horse’s speed is less than or equal to the horse at the top of the stack, it can never overtake and is discarded.
  • If the current horse’s speed is greater than the top horse’s, calculate when it will overtake the current leader.
  • If the calculated overtaking time is invalid (e.g., earlier than the previous overtaking time), adjust the stack by removing horses that can no longer lead.

Handling Queries:

Use binary search to handle each query time t in the times list to find the corresponding leading horse.
bisect.bisect_right(times, t) - 1 finds the first time point greater than t, then subtract one to get the corresponding horse index.

Timeline Construction: We build a timeline that records the time points when the leading horse changes and the horse that leads during that period.

Binary Search for Queries: Since the timeline is sorted chronologically, we can efficiently find the leading horse for each query time using binary search.

Codes:

n, q = map(int, input().split())
s_list = list(map(int, input().split()))
v_list = list(map(int, input().split()))
t_list = list(map(int, input().split()))

horses = list(zip(range(n), s_list, v_list))
# Sort horses by decreasing s_i
horses.sort(key=lambda x: (-x[1], -x[2]))  # (-s_i, -v_i)

stack = []
# 存储每次马匹变化的时间点
times = []
# 存储每次马匹变化的编号
horse_indices = []

for idx, s_i, v_i in horses:
    discard = False
    # 检查是否可以领先
    while stack:
        # 看看顶部
        jdx, s_j, v_j = stack[-1]
        if v_i <= v_j:
            # 如果它的速度小于或等于当前领导者的速度，它永远无法超越并被丢弃。
            discard = True
            break
        else:
            # Compute t_int
            t_prev = times[-1] if times else 0.0
            # 可能超过的时间
            t_int = (s_j - s_i) / (v_i - v_j)
            if t_int <= t_prev:
                stack.pop()
                times.pop()
                horse_indices.pop()
            else:
                break
    if not discard:
        if stack:
            t_int = (s_j - s_i) / (v_i - v_j)
        else:
            t_int = 0.0
        stack.append((idx, s_i, v_i))
        times.append(t_int)
        horse_indices.append(idx)


import bisect

result = []
for t in t_list:
    idx = bisect.bisect_right(times, t) -1
    idx = max(0, idx)
    result.append(horse_indices[idx]+1)  # +1 to convert to 1-based indexing

print(' '.join(map(str, result)))