Submission #1087518

#TimeUsernameProblemLanguageResultExecution timeMemory
1087518YannickOfungiArchery (IOI09_archery)Cpython 3
0 / 100
19 ms3692 KiB
import sys
import threading

def main():
    import sys
    input = sys.stdin.readline

    N, R = map(int, sys.stdin.readline().split())
    R0 = int(sys.stdin.readline())  # Our rank
    other_ranks = []
    for _ in range(2*N - 1):
        other_ranks.append(int(sys.stdin.readline()))
    # Arrange other archers into targets
    better_archers_count_per_target = [0] * (N + 2)  # 1-indexed, up to N
    for t in range(1, N+1):
        idx1 = 2*(t-1)  # positions in other_ranks list (0-based)
        idx2 = 2*(t-1) + 1
        count = 0
        if idx1 < len(other_ranks) and other_ranks[idx1] < R0:
            count += 1
        if idx2 < len(other_ranks) and other_ranks[idx2] < R0:
            count += 1
        better_archers_count_per_target[t] = count
    # Compute suffix sums
    suffix_sum_better_archers = [0] * (N + 2)  # indices from 1 to N+1
    for t in range(N, 0, -1):
        suffix_sum_better_archers[t] = suffix_sum_better_archers[t+1] + better_archers_count_per_target[t]
    # Find the best starting target
    min_finishing_target = float('inf')
    best_t = -1
    for t in range(1, N+1):
        finishing_target = t + suffix_sum_better_archers[t+1]
        if finishing_target < min_finishing_target:
            min_finishing_target = finishing_target
            best_t = t
        elif finishing_target == min_finishing_target and t > best_t:
            best_t = t
    print(best_t)

threading.Thread(target=main).start()
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...