自分用メモ

プログラミングとかのメモを書きたいです

競プロ典型 90 問:044 - Shift and Swapping(★3)

問題

atcoder.jp

挑戦結果

  • 挑戦日:2021/10/17
  • 結果:解けた
  • 時間:10分

考えたこと

  • T1とT3はやるだけ。
  • T2は右シフトを愚直に実装するとTLEしそう。N=10^ 5, Q=10^ 5 なので、シフトに N、クエリ数がQだと 10^{10}でまずそう。
  • シフトの代わりに基準にする場所を持っておいて、T2のときに基準をずらせば良さそう。T1とT3はその基準からの相対位置でやる。

公式解説

https://twitter.com/e869120/status/1395148057730187265

解説を読んだふりかえり

  • 特に問題なかった

ソース

N,Q = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
# シフトは重いので、代わりに基準の場所を決めておく
d = 0
for _ in range(Q):
    T,x,y = [int(x) for x in input().split()]
    # 基準と0-indexの調整
    x = (x -1 + d) % N
    y = (y -1 + d) % N
    if T==1:
        # 入れ替える
        A[x], A[y] = A[y], A[x] 
    elif T==2:
        # シフトの代わりに基準をずらす
        d+=(N-1)
    elif T==3:
        print(A[x])