C17 - Strange Data Structure? Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 1000 点

問題文

あなたはアトラクションの行列を管理しています。最初、行列には誰も並んでいません。これから Q 個のクエリを処理する必要があります。各クエリは以下の 4 種類のいずれかです。

  • タイプ A: 文字列 X_i が与えられ、行列の最後尾に名前が X_i である人が入る。
  • タイプ B: 文字列 X_i が与えられ、行列の中央に名前が X_i である人が入る。
  • タイプ C: 行列の先頭にいる人が列から抜ける。
  • タイプ D: 行列の先頭にいる人の名前を答える。

ただし、タイプ B のクエリでは、行列に並んでいる人が n 人であるとき、n が奇数のときは先頭から (n+1)/2 人目の後ろに、n が偶数のときは先頭から n/2 人目の後ろに入るものとします（特に n = 0 の場合は、行列の最後尾に入ることになります）。

すべてのクエリを順番に処理し、与えられるタイプ D のクエリに正しく答えるプログラムを作成してください。

注意

この問題では実行時間制限に間に合えば正解 (AC) とはなりますが、計算量 O(Q) で解いてみましょう。

制約

  • 2 \leq Q \leq 300000
  • i 個目のクエリがタイプ A, B のとき、X_i は英小文字からなる 10 文字以下の文字列
  • 行列に誰も並んでいない状態でタイプ C, D のクエリが行われることはない
  • タイプ D のクエリは 1 回以上行われる

入力

入力は以下の形式で標準入力から与えられます。

Q
Query_1
Query_2
 \vdots
Query_Q

ただし、Query_i は i 番目のクエリの情報を指します。各タイプについて以下の形式で与えられます。

タイプ A のとき

A X_i

タイプ B のとき

B X_i

タイプ C のとき

C

タイプ D のとき

D

出力

タイプ D のクエリが来るたびに、行列の先頭ににいる人の名前を 1 行ずつ出力してください。

入力例 1

6
A kyopuro
A tessoku
B book
D
C
D

出力例 1

kyopuro
book

各クエリとその結果は以下のようになります。

何番目 クエリ 説明 行列
1 A kyopuro 行列の末尾に kyopuro さんが入る [ "kyopuro" ]
2 A tessoku 行列の末尾に tessoku さんが入る [ "kyopuro", "tessoku" ]
3 B book 行列の中央に book さんが入る [ "kyopuro", "book", "tessoku" ]
4 D 行列の先頭の人の名前を答える （kyopuro と出力する）
5 C 行列の先頭の人が列から抜ける [ "book", "tessoku" ]
6 D 行列の先頭の人の名前を答える （book と出力する）

したがって、1 行目に kyopuro、2 行目に book と出力します。

入力例 2

15
B prefixsum
B binsearch
A dp
B math
C
D
C
D
B heuristics
B ds
B graph
C
D
C
D

出力例 2

binsearch
math
heuristics
graph