はまやんはまやんはまやん

hamayanhamayan's blog

String Formation [AtCoder Beginner Contest 158 D]

https://atcoder.jp/contests/abc158/tasks/abc158_d

解説

https://atcoder.jp/contests/abc158/submissions/10644638

実装問題。
各クエリO(1)くらいでやりたい所。
先頭と末尾に追加クエリがある。
先頭と末尾に追加するという操作ができるデータ構造がある。dequeだ。

dequeで実装を進めていく。
文字列が反転されているかを示すフラグを用意しておく。
isRev := 文字列が反転されているか

T=1のときは、isRevを反転させるだけ
T=2のときは、isRevがtrueになっているなら追加場所を逆転させる。
そうでないなら、クエリ通りに追加してやる感じ。

答えの文字列をdequeから再構成するが、isRevの値を見て、先頭からか末尾からか
どちらかから順番にとってきて答える。

string S; int Q;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> Q;

    deque<char> deq;
    fore(c, S) deq.push_back(c);
    bool isRev = false;

    rep(_, 0, Q) {
        int t; cin >> t;
        if (t == 1) isRev = !isRev;
        else {
            int f; char c; cin >> f >> c;

            if (f == 1) {
                if (isRev) deq.push_back(c);
                else deq.push_front(c);
            }
            else {
                if (isRev) deq.push_front(c);
                else deq.push_back(c);
            }
        }
    }

    string ans = "";
    if (isRev) {
        while (!deq.empty()) {
            ans += deq.back();
            deq.pop_back();
        }
    }
    else {
        while (!deq.empty()) {
            ans += deq.front();
            deq.pop_front();
        }
    }

    cout << ans << endl;
}