Submission #1087515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087515		YannickOfungi	Archery (IOI09_archery)	Cpython 3	0 / 100	19 ms	3688 KiB

archery

# Read input
import sys
import threading

def main():
    import sys

    sys.setrecursionlimit(1 << 25)
    N, R = map(int, sys.stdin.readline().split())
    R0 = int(sys.stdin.readline())
    positions = []
    for _ in range(2*N -1):
        positions.append(int(sys.stdin.readline()))

    better_archers_starting_positions = [0] * (2*N -1)
    for i in range(2*N -1):
        if positions[i] < R0:
            better_archers_starting_positions[i] = 1

    better_archers_starting_targets = [0] * N
    for t in range(N):
        pos1 = 2*t
        pos2 = 2*t +1
        if pos1 < 2*N -1:
            better_archers_starting_targets[t] += better_archers_starting_positions[pos1]
        if pos2 < 2*N -1:
            better_archers_starting_targets[t] += better_archers_starting_positions[pos2]

    suffix_sum_better = [0] * (N+1)
    for t in range(N-1, -1, -1):
        suffix_sum_better[t] = suffix_sum_better[t+1] + better_archers_starting_targets[t]

    min_finishing_target = float('inf')
    best_t = -1
    for t in range(1, N+1):
        N_better_right = suffix_sum_better[t]
        finishing_target = t + N_better_right
        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()

• Subtask 1: 0 / 6
• Subtask 2: 0 / 94