5 - Накопитель

#include <bits/stdc++.h>
using namespace std;
#define DB(v) cerr << #v << ' ' << v << endl
#define sz(v) int(v.size())
#define For(i, a, b) for(int i = a;i <= b; ++i)

const int N = 1e5;

template <typename T>
inline ostream &operator << (ostream &out, const vector <T> &v) {
    for(auto to: v)
        out << to << ' ';
    out << '\n';
    return out;
}

vector <int> arr, index_arr;
string symbol;

string s, t;

void make_arr () {
    arr.clear();
    index_arr.resize(sz(s));
    symbol = "";
    for(int i = 0;i < sz(s); ++i) {
        int j = i;
        while(j < sz(s) - 1 && s[j + 1] == s[j])
            j++;
        arr.push_back(j - i + 1);
        for(int k = i;k <= j; ++k)
            index_arr[k] = sz(arr) - 1;
        symbol += s[i];
        i = j;
    }
}

int oper = 0;

bool can(int l_border, int r_border, int i, char need) {
    if(symbol[i] != need)
        return false;

    int l = i - 1, r = i + 1, amount = arr[i];
    while(l >= l_border || r <= r_border) {
        oper++;
        bool found = false;
        if(l >= l_border && amount > arr[l]) {
            found = true;
            amount += arr[l];
            if(l > l_border)
                amount += arr[l - 1];
            l -= 2;
        }
        if(r <= r_border && amount > arr[r]) {
            found = true;
            amount += arr[r];
            if(r + 1 <= r_border)
                amount += arr[r + 1];
            r += 2;
        }
        if(!found)
            return false;
    }
    return true;
}

bool good (int l, int r) {
    if(l != 0 && s[l] != t[l])
        return false;
    if(r != sz(s) - 1 && s[r] != t[r])
        return false;
    int l_border = index_arr[l], r_border = index_arr[r];
    char need = t[l];

    DB(l_border); DB(r_border);
    for(int i = l_border; i <= r_border; ++i) {
        if(can(l_border, r_border, i, need)) {
            return true;
        }
    }
    return false;
}

void generate_input() {
    s = "";
    string add = "++-";
    while(sz(s) + 3 < N / 2) {
        s += add;
    }
    for(int i = 0;i < N / 2; ++i)
        s += '-';

    t = "";
    for(int i = 0;i < sz(s); ++i)
        t += '+';
}

int main()
{
#ifdef HOME
    freopen("input.txt","r",stdin);
#endif // HOME
    ios::sync_with_stdio(NULL); cin.tie(NULL);
    int Q; cin >> Q;
    For(q, 1, Q) {
        //cin >> s >> t;
        generate_input();
       // cout << s << endl << t << endl;
        DB(sz(s)); DB(sz(t));
        make_arr();

        bool ans = true;
        for(int i = 0;i < sz(t); ++i) {
            int j = i;
            while(j + 1 < sz(t) && t[j + 1] == t[j]) {
                j++;
            }
            if(!good(i, j)) {
                ans = false;
                break;
            }
            i = j;
        }
        DB(oper);

        if(ans)
            cout << "Yes";
        else
            cout << "No";
        cout << '\n';
    }
    return 0;
}