Sorting

#include <bits/stdc++.h>
#define X first
#define Y second
#define sz(a) (int)a.size()
#define pb push_back

using namespace std;
typedef long long ll;

void solve();

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

int a[110];

set <string> s;

void solve() {
    s.clear();
    string ans, t;
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        t.pb((char)('0' + a[i]));
        ans.pb((char)('0' + i + 1));
    }
    s.insert(t);
    deque <string> d = {t};
    int cnt = 0;
    while (sz(d) > 0) {
        cnt++;
        if (cnt == 400)
            break;
        auto r = d.front();
        if (ans == r) {
            cout << "YES\n";
            return;
        }
        d.pop_front();
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 2; j < n - 1; ++j) {
                swap(r[i], r[j]);
                swap(r[i + 1], r[j + 1]);
                if (s.count(r) == 0) {
                    s.insert(r);
                    d.pb(r);
                }
                swap(r[i], r[j]);
                swap(r[i + 1], r[j + 1]);
            }
        }
    }
    cout << "NO\n";
    return;
}

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: TIME LIMIT EXCEEDED