Sorting

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define pb push_back

const int MAX_N = 100;
int p[1 + MAX_N];

map <vector <int>, bool> seen;
bool found;
void bkt (vector <int> v) {
    if (found) return;
    if (seen[v])
        return;
    seen[v] = true;
    int n = v.size ();
    bool good = true;
    for (int i = 0; i < n; i++)
        if (v[i] != i + 1)
            good = false;
    if (good)
        found = true;
    if (found)
        return;
    for (int i = 0; i + 1 < n; i++)
        for (int j = i + 2; j + 1 < n; j++) {
            vector <int> new_v = v;
            swap (new_v[i], new_v[j]);
            swap (new_v[i + 1], new_v[j + 1]);
            bkt (new_v);
        }
}

void solveTest () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    if (n <= 6) {
        vector <int> v;
        seen.clear ();
        found = false;
        for (int i = 1; i <= n; i++)
            v.pb (p[i]);
        bkt (v);
        if (found)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    else {
        int inv = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                if (p[i] > p[j])
                    inv++;
        if (inv & 1)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

int main () {
    int t;
    cin >> t;
    while (t--)
        solveTest ();
    return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED