Sorting

#include <bits/stdc++.h>
using namespace std;
 
set<int> vis;
int geh(const vector<int>& v) {
  int num = 0;
  const int n = (int)v.size();
  for (int i = 0; i < n; ++i) {
    num *= 10;
    num += v[i];
  }
  return num;
}
 
int sz;
void go(vector<int>& arr) {
  int h = geh(arr);
  if (vis.find(h) != vis.end()) return;
  vis.insert(h);
  for (int i = 0; i < sz; ++i) {
    for (int j = 2+i; 1+j < sz; ++j) {
      swap(arr[i], arr[j]);
      swap(arr[1+i], arr[1+j]);
      go(arr);
      swap(arr[i], arr[j]);
      swap(arr[1+i], arr[1+j]);
    }
  }
}
 
bool good(const vector<int>& a) {
  const int n = (int)a.size();
  if (n <= 3) return is_sorted(a.begin(), a.end());
  if (n == 4) {
    return is_sorted(a.begin(), a.end()) || a == vector<int>({3,4,1,2});
  }
  bool x = n&1;
  int f = a.front();
  vector<int> v;
  for (int i = 1; i < n; ++i) {
    if (a[i] > f) v.push_back(a[i]-1);
    else v.push_back(a[i]);
  }
  return x ^ good(v);
}
 
int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  vector<int> arr;
  int tc; cin >> tc;
  while (tc--) {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    cout << (good(a) ? "YES" : "NO") << '\n'; 
  }
  return 0;
}

Test 1

Group: 1, 2

Verdict: WRONG ANSWER

Test 2

Group: 2

Verdict: WRONG ANSWER

Test 3

Group: 1, 2

Verdict: WRONG ANSWER

Test 4

Group: 1, 2

Verdict: WRONG ANSWER