Sorting

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = a - 1; i >= (b); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set
#define INF 1000000000

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    pair<string, uset<string>> vis[1001];
    umap<string, int> prev;
    int tc, n;
    cin >> tc;
    while (tc--) {
        cin >> n;
        string nums(n, 0);
        rep(i, 0, n) cin >> nums[i];
        if (prev.count(nums)) {
            cout << vis[prev[nums]].first<<'\n';
            continue;
        }

        queue<string> q;
        q.push(nums);
        vis[tc].second.insert(nums);
        string ans = "NO", goal = string(n, ' ');
        rep(i, 0, n) goal[i] = '1' + i;

        while (!q.empty()) {
            nums = q.front();
            q.pop();
            prev.emplace(nums, tc);
            if (nums == goal) {
                ans = "YES";
                while (!q.empty()) q.pop();
                continue;
            }

            rep(i, 0, n - 3) {
                string next;
                rep(j, i + 2, n - 1) {
                    next = nums;
                    swap(next[i], next[j]);
                    swap(next[i + 1], next[j + 1]);
                    if (!vis[tc].second.count(next)) {
                        vis[tc].second.insert(next);
                        q.push(next);
                    }
                }
            }
        }

        vis[tc].first = ans;
        cout << ans << '\n';
    }
    return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED