atcoder 158 D問題が解けません。

Question

atcoder の問題を解いているのですが、実行時エラーとなってしまいます。
なぜエラーになるかわからないので教えてくれるとうれしいです。

問題

atcoder のABC158 D問題
https://atcoder.jp/contests/abc158/tasks/abc158_d

コード

#include<iostream>
#include<algorithm>
using namespace std;
#include<string>

int main(){
    string s; cin >> s;
    int q; cin >> q;
    int t[s.length()], f[s.length()], flag = 1;
    string c[s.length()], top="";
    for(int i=0; i<q; i++){
        cin >> t[i];
        if(t[i] == 1) continue;
        cin >> f[i] >> c[i];
        if(f[i] == 2) f[i] = -1;
    }
    for(int i=0; i<q; i++){
        if(t[i] == 1){
            flag *= -1;
        }else{
            if(flag * f[i] == 1) top.append(c[i]);
            else s.append(c[i]);
        }
    }
    reverse(top.begin(), top.end());
    top.append(s);
    if(flag == -1) reverse(top.begin(), top.end());
    cout << top << endl;
    return 0;
}

Answer 1

    int t[s.length()], f[s.length()], flag = 1;
    string c[s.length()], top="";

この配列の長さはq必要ではないですか?

Comments

[goro_gnm]

あ、そうですね！ありがとうございます！

Answer 2

普通に考えるとこんな感じになると思うんですけど、なんか変なソースになってませんか？

＃コンパイル通るコードだと怒られそうなので、ニュアンスだけ

if (t == 1) reverse;
if (t == 2 && f == 1) insert(0, x);
if (t == 2 && f == 2) insert(length, x);

Comments

[goro_gnm]

string に対して、先頭にinsertするのと前後を反転させるのを毎回実行するのは計算量が多すぎて時間超過になってしまうのではと思います。
なので各クエリに対してstringの末尾に文字列を挿入する（またはしない）だけでこと足りるように書きました。

[izmktr]

もしかして、先頭挿入は時間がかかるけど、反転は時間がかからないと思ってます？
代入の数でいうと、先頭挿入はn+2、反転はn*1.5かかりますよ？
文字列長が1MBレベルなら差として出てきますが、通常だとほぼ0コストです
どうしてもそこに時間がかかって時間超過するのなら、dequeを使えばいいです

[goro_gnm]

いや、先頭挿入も反転も時間がかかると思っています。
それらに対し末尾挿入はo(1)であるので、末尾挿入を使ったという趣旨でした。

問題文には
1 < |S| < 10^5
1 < Q < 2 * 10^5
とあり、各クエリで反転させることをすると最大o((S+Q)*Q)であるため、今回に関しては0コストとは言えない状況になると思います。