![見出し画像](https://assets.st-note.com/production/uploads/images/86229285/rectangle_large_type_2_75f956f35fc1dc0bff853a6056354a92.png?width=1200)
Photo by
ia19200102
ほぼ日刊競プロ ABC199 C - IPFL
問題文
長さ 2N の文字列 S があります。
この文字列に対して Q 個のクエリが与えられます。i 番目のクエリでは 3 つの整数 Ti,Ai,Biが与えられるので、以下の処理をします。Ti=1 のとき : S の Ai文字目と Bi文字目を入れ替えるTi=2 のとき : S の前半 N 文字と後半 N 文字を入れ替える(Ai,Biの値は用いない)
例えば S が FLIP のときにこのクエリを処理すると、S は IPFL となる。
これら Q 個のクエリを与えられた順に全て処理した後の S を出力してください。
考えたこと
ただ実装するとTLEになってしまう.それはTi=2の時の入れ替えにO(N)かかってしまうため,Ti=2の時の処理を考える.
2
FLIP
2
2 0 0
1 1 4
という例の場合,最終的な結果LPFIと最初のFLIPから規則性を探す.
それぞれFは1→3,Lは2→1,Iは3→4,Pは4→2と動いている.前後を入れ替えてから1,1,4というクエリに関しては1番目(F)が1+N,4番目(P)が4-N動いているLとIは最後だけ1回前を入れ替えれば良いので
N=int(input())
S=list(input())
Q=int(input())
S.insert(0,"0")
flag = True
ans = []
for i in range(Q):
T,A,B = map(int,input().split())
#print (S[N:2*N])
if T==2:
if flag:
flag =False
else:
flag =True
elif T==1:
if flag:
S[A],S[B]=S[B],S[A]
#A,BがNより大きいか小さいかで,A,Bの移動距離を変える
else:
if A<=N:
A+=N
else:
A-=N
if B<=N:
B+=N
else:
B-=N
S[A],S[B]=S[B],S[A]
left = S[1:N+1]
right = S[N+1:2*N+1]
#Nを境に入れ替える
if flag ==True:
ans = left+right
else:
ans = right+left
print ("".join(ans))
この記事が気に入ったらサポートをしてみませんか?