結果

問題 No.1097 Remainder Operation
ユーザー lam6er
提出日時 2025-03-20 18:44:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 138 ms / 2,000 ms
コード長 1,523 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 124,276 KB
最終ジャッジ日時 2025-03-20 18:45:03
合計ジャッジ時間 4,295 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    # Precompute the history and detect cycle
    history = [0]  # history[0] is after 0 operations
    visited = [-1] * N
    cycle_start = -1
    cycle_length = 0
    cycle_sum = 0
    found_cycle = False

    for step in range(0, N + 1):  # step is the index in history (number of steps done)
        if step >= len(history):
            break
        current_X = history[step]
        r = current_X % N
        if visited[r] != -1:
            # Found a cycle
            prev_step = visited[r]
            cycle_start = prev_step
            cycle_length = step - prev_step
            cycle_sum = history[step] - history[prev_step]
            found_cycle = True
            break
        visited[r] = step
        new_X = current_X + A[r]
        history.append(new_X)

    for K in queries:
        if not found_cycle or K < len(history):
            print(history[K])
        else:
            # Calculate based on the cycle
            remaining = (K - cycle_start) % cycle_length
            full_cycles = (K - cycle_start) // cycle_length
            total = history[cycle_start] + full_cycles * cycle_sum
            total += (history[cycle_start + remaining] - history[cycle_start])
            print(total)

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