Sorting

input/code.cpp: In function 'int main()':
input/code.cpp:120:10: warning: unused variable 'b' [-Wunused-variable]
     ll a,b,c,d;
          ^
input/code.cpp:120:12: warning: unused variable 'c' [-Wunused-variable]
     ll a,b,c,d;
            ^
input/code.cpp:120:14: warning: unused variable 'd' [-Wunused-variable]
     ll a,b,c,d;
              ^

#pragma GCC optimize("O3")   //
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, b, a) for(int i = b - 1; i >= a; i--)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef long double ld;
typedef unsigned long long ull;

unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937 eng(seed);

ll random2(){
    return (1ll << 31ll)*eng()+eng();
}

ll n,m,k,q,T;

const ll big = 1000000007;
const ll big2 = 1000000009;
const ll mod =  998244353;

const int MAXN = 400002;

vi A;

void answer(bool ans){
    if(ans){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
}

set<ll> S;

ll has(vi &P){
    ll h = sz(P);
    trav(a, P){
        h *= 101;
        h += a+1;
    }
    return h;
}

int inv(vi &V){
    int ans = 0;
    rep(c1,0,sz(V)){
        rep(c2,0,c1){
            if(V[c2] > V[c1])ans++;
        }
    }
    return ans;
}

ll F[123] = {0};

void bfs(int k){
    queue<vi> Q;
    vi temp;
    rep(c1,0,k){
        temp.push_back(c1);
    }
    Q.push(temp);
    while(!Q.empty()){
        vi V = Q.front();
        Q.pop();
        ll h = has(V);
        if(S.find(h) != S.end())continue;
        S.insert(h);
        F[k]++;

        /*
        if(k == 5){
            rep(c3,0,k){
                cerr << V[c3]+1 << " ";
            }cerr << inv(V)%2 << "  hh\n";
        }
        */

        vi temp2;
        rep(c1,0,k){
            temp2.push_back(V[c1]);
        }
        rep(c1,0,k-3){

            rep(c2,c1+2,k-1){
                swap(temp2[c1], temp2[c2]);
                swap(temp2[c1+1], temp2[c2+1]);
                ll h2 = has(temp2);

                if(S.find(h2) == S.end()){
                    Q.push(temp2);
                }
                swap(temp2[c1], temp2[c2]);
                swap(temp2[c1+1], temp2[c2+1]);
            }

        }
    }

}

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

    //freopen("fhc.txt","r",stdin);
    //freopen("autput.txt","w",stdout);

    ll a,b,c,d;

    const int lim = 8;

    rep(c1,4,lim+1){
        bfs(c1);
        cerr << c1 << ": " << F[c1] << "\n";
    }

    cin >> T;

    rep(c4,0,T){

        cin >> n;
        A.clear();
        int invs = 0;

        rep(c1,0,n){
            cin >> a;
            a--;
            A.push_back(a);
            rep(c2,0,c1){
                if(A[c2] > a)invs++;
            }
        }

        if(n <= 3){
            answer((invs == 0));
            continue;
        }

        if(n >= 4){
            if(n <= lim){
                ll h = has(A);
                if(S.find(h) == S.end()){
                    answer(0);
                }
                else{
                    answer(1);
                }
                continue;
            }
            answer((1+invs)%2);

        }

    }
    return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

4: 2
5: 60
6: 360
7: 2520
8: 20160

Test 2

Group: 2

Verdict: ACCEPTED

4: 2
5: 60
6: 360
7: 2520
8: 20160

Test 3

Group: 1, 2

Verdict: ACCEPTED

4: 2
5: 60
6: 360
7: 2520
8: 20160

Test 4

Group: 1, 2

Verdict: ACCEPTED

4: 2
5: 60
6: 360
7: 2520
8: 20160