Sorting

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<int,int> pi;

vector<int> nums, pos;
//{a-1, a}, {b-1,b}
void sw(int a, int b){
    int pa = pos[a], pb = pos[b];
    swap(pos[nums[pa-1]],pos[nums[pb-1]]);
    swap(nums[pa-1], nums[pb-1]);
    swap(nums[pa], nums[pb]);
    swap(pos[a], pos[b]);
}
vector<int> go = {
1234,
3412,
1423,
3241,
2314,
4132,
4321,
2143,
2431,
4213,
3124,
1342};
vector<bool> found(10000,0);
int vtoi(){
    int ans = 0;
    for(int i = 1; i <= 4; i++){
        ans *= 10; ans += nums[i];
    }
    return ans;
}

//void gothr(){
//    int cur = vtoi();
//    if(found[cur]) return;
//    found[cur] = 1;
//    if(cur%10000 == 5678) cout << cur/10000 << "\n";
//    for(int i = 2; i <= 8; i++){
//        for(int j = i+2; j <= 8; j++){
//            vector<int> tempn = nums, tempp = pos;
//            sw(i,j);
//            gothr();
//            nums = tempn; pos = tempp;
//        }
//    }
//}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for(auto &a: go) found[a] = 1;
    while(t--){
        int n; cin >> n;
        nums.resize(n+1), pos.resize(n+1);
        for(int i = 1; i <= n; i++) cin >> nums[i];
        for(int i = 1; i <= n; i++) pos[nums[i]] = i;
        int n2 = n;
        for(; n2 > 4; n2--){
            if(pos[n2] == n2) continue;
            if(pos[n2] > 3){
                sw(n2,nums[2]);
            }else if(pos[n2] == 1){
                sw(nums[2], nums[4]);
            }
            sw(n2, nums[n2]);
        }
        bool good = 1;
        for(int i = 1; i <= n2; i++){
            if(pos[i] != i) good = 0;
        }
        if(n == 4){
            if(vtoi() == 3412) good = 1;
        }else if(n2 == 4){
            if(found[vtoi()]) good = 1;
        }
        if(good) cout << "YES\n";
        else cout << "NO\n";
    }
//    nums = {0,1,2,3,4,5,6,7,8};
//    pos = {0,1,2,3,4,5,6,7,8};
//    gothr();
    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