Enumeration

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define D(x) {x;}
#else
#define D(x)
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x),end(x)
#define sz(x) (int) (x).size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

int n;
string buf;

set<string> visited;

void act(int a, int b) {
    cout << a+1 << " " << b+1 << endl;
    assert(buf[a] != buf[b]);
    swap(buf[a], buf[b]);
    D(cout << buf << endl);
    D(
            if (visited.count(buf)) {
                assert(false);
            }
            visited.insert(buf);
     );
}

bool valid(int x, int h) {
    if (h < 0) return false;
    if (h > x) return false;
    if (h > n-x) return false;
    return true;
}

void f(bool up, int lock, int h) {
    if (h == 0) {
        lock++;
        h++;
    }
    if (lock+1 >= n) return;
    int sum = 0;
    for (int i = 0; i < lock; ++i) {
        if (buf[i] == '(') sum++;
        else sum--;
    }
    assert(sum == h);
    D(cout << "ENTER f" << up << " " << lock << " " << h << endl);
    if (up) {
        // PRECONDITION: suffix is down
        // for (int i = lock; i < n; ++i) assert(buf[i] == (i%2 ? ')' : '('));
    } else {
        // PRECONDITION: suffix is up
        for (int i = lock; i < n-1; ++i) assert(!(buf[i] == ')' && buf[i+1] == '('));
    }
    if (up) {
        int nlock = lock+1;
        int nh = h-1;
        int nup = up;
        while (valid(nlock, nh) && nh < n-nlock) {
            f(nup, nlock, nh);
            int a = nlock-1;
            int b = a;
            while (b < n && buf[b] == ')') b++;
            assert(b < n);
            D(cout << "of " << up << " " << lock << " " << h << ": " << nlock << " " << nh << " " << nup << endl;)
            act(a, b);
            nup ^= 1;
            nlock++;
            nh++;
        }
    } else {
        int nlock = lock;
        int nh = h;
        int nup = up;
        while (valid(nlock+1, nh+1)) nlock++, nh++;
        // PARITY CHECK
        int steps = nlock - lock;
        int par = steps%2;
        if (!par) nup = !nup;
        D(cout << "steps " << steps << " " << par << " " << nup << endl;)
        while (nlock > lock) {
            D(cout << "dw " << nlock << " " << nh << " " << nup << endl;)
            if (!nup) {
                act(nlock-1, nlock);
            } else {
                int a = nlock-1;
                // XXX
                int b = a+1;
                while (b < n && buf[b] == ')') b++;
                b -= 2;
                // if (a >= b) break;
                act(a, b);
            }
            f(nup, nlock, nh-2);
            nup ^= 1;
            nlock--;
            nh--;
        }
    }
    D(cout << "LEAVE f" << up << " " << lock << " " << h << endl);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n;
    buf = string(n, 0);
    for (int i = 0; i < n; ++i) buf[i] = i%2 ? ')' : '(';
    visited.insert(buf);
    cout << buf << endl;
    f(1, 0, 0);
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED