стресс тесты скобки

// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("avx")

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <set>
#include <queue>

#include <cstdio>
#include <cmath>

using namespace std;

vector<string> psp;

void gen(string s, int open, int close) {
    if (open + close == 8) {
        psp.push_back(s);
        return;
    }
    if (open < 4) gen(s + '(', open + 1, close);
    if (open > close) gen(s + ')', open, close + 1);
}

string andr(string a, string b) {
    int n = 8;
    int bl1=0;
    int bl2=0;
    int p1=0;
    int p2=0;
    int k=0;
    for (int i = 0; i < n; i++) {
        if (bl1 < 0 || bl2 <0) {
            ///cout << "NO" << endl;
            k=1;
            return "NO";
        }
        if (a[i] == '(') {
            bl1++;
            p1++;
        }
        else {
            bl1--;
        }

        if (b[i] == '(') {
            bl2++;
            p2++;
        }
        else {
            bl2--;
        }
        if ( (p1 < n/2 && p2 < n/2) || (p1 >= n/2 && p2 >= n/2) ) {
            if (a[i]!=b[i]) {
                if (bl1 > bl2 && b[i]==')' ) {
                    bl1-=2;
                    bl2+=2;
                    p2++;
                }
                else if (bl1 < bl2 && a[i]==')' ) {
                    bl2-=2;
                    bl1+=2;
                    p1++;
                }
            }
        }
        else if (p1 < n/2 && p2>=n/2) {
            if (a[i] != b[i] && a[i] == ')') {
                p1++;
                p2--;
                bl1+=2;
                bl2-=2;
            }
        }
        else if (p1 >= n/2 && p2 < n/2) {
            if (a[i] != b[i] && b[i] == ')') {
                p2++;
                p1--;
                bl2+=2;
                bl1-=2;
            }
        }
    }
    if (bl1==0 && bl2==0) {
        ///cout <<"YES" << endl;
        return "YES";
    }
    else if (k==0) {
        ///cout << "NO" << endl;
        return "NO";
    }
}

string avt(string s, string t) {
    int n = 8;
    string r1 = "", r2 = "";
    bool bj = 1;
    for (int i = 0; i < n; i++) {
        if (s[i] == t[i]) r1 += s[i], r2 += t[i];
        else {
            if (bj) r1 += '(', r2 += ')';
            else r1 += ')', r2 += '(';
            bj ^= 1;
        }
    }
    int t1 = 0, t2 = 0;
    bj = 1;
    for (int i = 0; i < n; i++) {
        if (r1[i] == '(') ++t1; else --t1;
        if (r2[i] == '(') ++t2; else --t2;
        if (t1 < 0 || t2 < 0) bj = 0;
    }
    if (t1 != 0 || t2 != 0) bj = 0;
    if (bj) return "YES";
    else return "NO";

}


int main() {
    gen("", 0, 0);
    for (auto a : psp) {
        for (auto b : psp) {
            vector<int> diff;
            for (int i = 0; i < 8; i++) {
                if (a[i] != b[i]) diff.push_back(i);
            }
            for (int x = 1; x < (1 << (int)diff.size()); x++) {
                set<int> fdiff;
                for (int i = 0; i < (int)diff.size(); i++) {
                    if (x & (1 << i)) fdiff.insert(diff[i]);
                }
                string a1, b1;
                for (int i = 0; i < 8; i++) {
                    if (fdiff.count(i)) {
                        a1 += b[i];
                        b1 += a[i];
                    } else {
                        a1 += a[i];
                        b1 += b[i];
                    }
                }

                string AVT = avt(a1, b1);
                string ANDR = andr(a1, b1);
                if (ANDR[0] != AVT[0]) {
                    cout << AVT << ' ' << ANDR << endl;
                    cout << a1 << " " << b1 << endl;
                    cout << "------------\n";
                }
            }
        }
    }
    return 0;
}