Enumeration

input/code.cpp: In function 'void backtrack(int, int, int)':
input/code.cpp:48:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int ii = 1; ii < path.size(); ii++) {
      |                          ~~~^~~~~~~~~~~~~

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

int n;
vector<array<int, 3>> adj[1 << N];
// 0: open
// 1: close

bool check(int x) {
    int s = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (x >> i & 1) {
            s--;
        } else {
            s++;
        }
        if (s < 0) {
            return false;
        }
    }
    return s == 0;
}

int flip(int val, int x, int y) {
    assert(x != y);
    val ^= (1 << x);
    val ^= (1 << y);
    return val;
}

bool vis[1 << N];
vector<pair<int, int>> path;
void backtrack(int u, int i, int j) {
    // cerr << u << '\n';
    int cnt = 0;
    for (auto [v, ii, jj] : adj[u]) {
        if (vis[v]) continue;
        cnt++;
    }
    if (cnt == 0) {
        cout << string(n/2, '(');
        cout << string(n/2, ')');
        cout << '\n';
        path.emplace_back(i, j);
        for (int ii = 1; ii < path.size(); ii++) {
            cout << path[ii].first + 1 << ' ' << path[ii].second + 1 << '\n';
        }
        exit(0);
    }

    vis[u] = 1;
    path.emplace_back(i, j);

    for (auto [v, ii, jj]: adj[u]) {
        if (vis[v]) continue;
        backtrack(v,ii,jj);
    }

    vis[u] = 0;
    path.pop_back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int val = 0; val < (1 << n); val++) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (check(flip(val, i, j))) {
                    adj[val].emplace_back(array<int, 3>{flip(val, i, j), i, j});
                }
            }
        }
    }

    int src = (1 << (n / 2)) - 1;
    backtrack(src,0,0);
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: TIME LIMIT EXCEEDED