結果

問題 No.1568 Sushi
ユーザー gew1fw
提出日時 2025-06-12 19:20:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,728 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 159,672 KB
最終ジャッジ日時 2025-06-12 19:21:08
合計ジャッジ時間 13,790 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample WA * 4
other WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff #

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    L = int(data[ptr])
    ptr += 1
    N = int(data[ptr])
    ptr += 1
    Q = int(data[ptr])
    ptr += 1
    A = list(map(int, data[ptr:ptr + N]))
    ptr += N

    phases = []
    for m in range(N + 1):
        if m == 0:
            start = 0
        else:
            start = A[m-1]
        if m < N:
            end = A[m]
        else:
            end = float('inf')
        if m % 2 == 0:
            direction = 1
        else:
            direction = -1
        phases.append((start, end, direction))

    D_prev = 0
    for query in range(Q):
        B_i = int(data[ptr])
        ptr += 1
        C_i = int(data[ptr])
        ptr += 1

        if query == 0:
            x_i = B_i
            t_i = C_i
        else:
            x_i = (B_i + D_prev) % L
            t_i = (C_i + D_prev) % (10**18)

        x = x_i
        current_time = t_i

        target = x % L

        m = bisect.bisect_right(A, current_time) if N > 0 else 0
        if m > N:
            m = N
        if N == 0:
            m = 0

        found = False
        while True:
            m = bisect.bisect_right(A, current_time) if N > 0 else 0
            if m > N:
                m = N

            if m < N:
                start = A[m-1] if m > 0 else 0
                end = A[m]
            else:
                start = A[-1] if N > 0 else 0
                end = float('inf')

            if current_time < start:
                end = start
            if current_time >= end:
                m += 1
                if m >= len(phases):
                    m = len(phases) - 1
                continue

            phase = phases[m]
            direction = phase[2]
            start_phase = phase[0]
            end_phase = phase[1]

            if current_time >= end_phase:
                m += 1
                continue

            max_time_in_phase = end_phase - current_time
            displacement = direction * max_time_in_phase
            total = displacement
            if (total % L + L) % L == target:
                delta = max_time_in_phase
                D = delta
                found = True
                break
            else:
                current_time = end_phase

            if end_phase == float('inf'):
                time_in_phase = (target - displacement) // direction
                if time_in_phase < 0:
                    time_in_phase = 0
                current_time += time_in_phase
                delta = current_time - t_i
                D = delta
                found = True
                break

        print(D)
        D_prev = D

if __name__ == '__main__':
    main()
0