競技プログラミングABC199C問題にて起きるTLEとなる原因について

Question

発生している問題・エラーメッセージ

Atcoder Beginer Contest 199 C問題 : https://atcoder.jp/contests/abc199/tasks/abc199_c
において以下のコードを書いて提出したのですが、TLEとなる理由についてわかりません。
ご教授ください。

エラーメッセージ: AC × 12, TLE × 10 

該当のソースコード

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<class T> inline bool chmax(T &a, T b) {if(a < b){a = b; return true;} return false;}
template<class T> inline bool chmin(T &a, T b) {if(a > b){a = b; return true;} return false;}
#define rep(i,n) for(int i = 0; i < (n); ++i)
const int INF = 2e9;


int main(){
    int N;
    cin >> N;

    string S;
    cin >> S;
    
    int Q;
    cin >> Q;

    int theFirst = 0;
    vector<string> s(2);
    rep(i,2){
        s[i] = "";
        for(int j = i*N; j < (i+1)*N; ++j){
            s[i] = s[i] + S[j];
        }
    }
    
    rep(q, Q){
        int T, A, B;
        cin >> T >> A >> B;
        --A; --B;
        if(T == 1){
            if(A < N && B < N){
                char temp = s[theFirst][A];
                s[theFirst][A] = s[theFirst][B];
                s[theFirst][B] = temp;
            }
            else if(A < N && N <= B){
                char temp = s[theFirst][A];
                s[theFirst][A] = s[(theFirst + 1) % 2][B-N];
                s[(theFirst + 1) % 2][B-N] = temp;
            }
            else{
                char temp = s[(theFirst + 1) % 2][A-N];
                s[(theFirst + 1) % 2][A-N] = s[(theFirst + 1) % 2][B-N];
                s[(theFirst + 1) % 2][B-N] = temp;
            }
        }
        else{
            theFirst = (theFirst + 1) % 2;
        }
    }

    cout << s[theFirst] + s[(theFirst + 1) % 2] << endl;
    return 0;
}

コードの説明

文字列 S を前半と後半に分けて配列 s にしまっています。 前半を theFirst で、後半を (theFirst + 1) % 2 で指しています。

Answer 1

文字列 S を前半と後半に分けるときに、1文字ずつ足していってるのが悪いのではないでしょうか。
substrあたりを使ったらどうでしょうか。

Comments

[ramu13]

そもそもクエリ前でTLEでしたか笑
盲点でした
ありがとうございます。

Answer 2

解決済みになっていますが、どのようにして解決したのでしょうか？

C++ の参考演算子 a ? b : c は、b と c が左辺値の時、結果も左辺値になるので
swap が使えて次のようなコードが書けます。

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

int main()
{
	int n, q;
	cin >> n;
	char *s = new char[n * 2 + 1], *s1 = s, *s2 = s + n;
	cin >> s >> q;
	while (--q >= 0) {
		int t, a, b;
		cin >> t >> a >> b;
		if (t == 1)
			swap(--a < n ? s1[a] : s2[a-n], --b < n ? s1[b] : s2[b-n]);
		else
			swap(s1, s2);
	}
	cout << string(s1, n) << string(s2, n) << endl;
	delete[] s;
}