Sorting

//sorting.cpp created at 01/29/21 21:00:48

#include <bits/stdc++.h>

using namespace std;

const int MN = 101;

int N;
int A[MN], B[MN];

void solve() {

}

int pack() {
    int ret = 0;
    for (int i=0; i<N; ++i) {
        ret *= 10;
        ret += B[i];
    }
    return ret;
}

void unpack(int ret) {
    for (int i=N-1; i>=0; --i) {
        B[i] = ret % 10;
        ret /= 10;
    }
}

set<int> seen;
bool brute() {
    copy(A, A+N, B);
    seen.clear();

    const int start = pack();
    
    for (int i=0; i<N; ++i) {
        B[i] = i+1;
    }
    const int tar = pack();

    queue<int> q;
    q.push(start);
    seen.insert(start);
    while (q.size() > 0) {
        const int cur = q.front(); q.pop();
        
        if (cur == tar) {
            return true;
        }

        for (int i=0; i+1<N; ++i) {
            for (int j=i+2; j+1<N; ++j) {
                unpack(cur);
                
                swap(B[i], B[j]);
                swap(B[i+1], B[j+1]);
                const int nxt = pack();
                if (seen.insert(nxt).second == true) {
                    q.push(nxt);
                }
            }
        }
    }
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int T;
    cin >> T;
    for (int t=1; t<=T; ++t) {
        cin >> N;
        for (int i=0; i<N; ++i) {
            cin >> A[i];
        }
        cout << (brute() ? "YES\n" : "NO\n");
    }
}

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