結果

問題 No.1568 Sushi
ユーザー lam6er
提出日時 2025-03-20 20:56:23
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,786 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,612 KB
実行使用メモリ 159,816 KB
最終ジャッジ日時 2025-03-20 20:56:53
合計ジャッジ時間 24,009 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff #

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    L = int(input[idx]); idx +=1
    N = int(input[idx]); idx +=1
    Q = int(input[idx]); idx +=1
    A = list(map(int, input[idx:idx+N]))
    idx +=N
    queries = []
    for _ in range(Q):
        B = int(input[idx])
        C = int(input[idx+1])
        idx +=2
        queries.append((B, C))
    
    D_prev = 0
    for i in range(Q):
        B, C = queries[i]
        if i == 0:
            x = B % L
            t = C
        else:
            x = (B + D_prev) % L
            t = (C + D_prev) % (10**15)
        
        s_candidates = [t]
        m = bisect.bisect_left(A, t)
        for k in range(2):
            if m + k < N:
                s_candidates.append(A[m + k])
        s_candidates = sorted(list(set(s_candidates)))
        min_arrival = float('inf')
        
        for s in s_candidates:
            if s < t:
                continue
            pos_m = bisect.bisect_right(A, s) -1
            num_revs = pos_m +1
            direction = num_revs %2
            sign = 1 if direction ==0 else -1
            
            disp_required = x % L
            current_disp = 0
            phase_index = pos_m +1
            total_T =0
            dir_sign = sign
            current_phase_start = s
            found = False
            phases_checked =0
            while phases_checked <4:
                if phase_index < N:
                    phase_end = A[phase_index]
                else:
                    phase_end = float('inf')
                phase_duration = phase_end - current_phase_start
                
                if dir_sign ==1:
                    req = disp_required
                else:
                    req = (L - disp_required) % L
                
                T_candidate = req
                if T_candidate <= phase_duration:
                    arrival_time = current_phase_start + T_candidate
                    min_arrival = min(min_arrival, arrival_time)
                    found = True
                    break
                else:
                    total_T += phase_duration
                    disp_required = (disp_required - dir_sign * phase_duration) % L
                    dir_sign *= -1
                    current_phase_start = phase_end if phase_index < N else float('inf')
                    phase_index +=1
                phases_checked +=1
            
            if not found:
                if phase_index >=N:
                    T_candidate = req
                    arrival_time = current_phase_start + T_candidate
                    min_arrival = min(min_arrival, arrival_time)
        
        D = min_arrival - t
        D_prev = D
        print(D)
    
if __name__ == '__main__':
    main()
0