Vaihdot

#include <iostream>
#include <vector>

using namespace std;

int t;
int n;
vector<int> v;
vector<pair<int, int>> s;

bool isSorted() {
  int x = v[0];
  for (int i = 1; i < n; i++) {
    if (v[i] < x) return false;
    else x = v[i];
  }

  return true;
}

void runSort() {
  if (isSorted()) return;
  s.clear();

  int x = 1;

  do {
    if (v[x-1] != x) {
      for (int i = n-1; i > -1; i--) {
        if (v[i] == x) {
          if (i == x) {
            if (i <= n-2) {
              // käytetään v[n-1] varastona
              int varasto = v[n-1];

              // eka vaihto
              v[n-1] = v[i];
              v[i] = varasto;

              s.push_back({ n, i+1});

              // toinen vaihto
              varasto = v[x-1];
              v[x-1] = v[n-1];
              v[n-1] = varasto;

              s.push_back({ n, x });

              // kolmas vaihto
              varasto = v[i];
              v[i] = v[n-1];
              v[n-1] = varasto;

              s.push_back({ n, i+1 });
            } else if (x > 2) {
              // käytetään v[0] varastona
              int varasto = v[0];

              // eka vaihto
              v[0] = v[i];
              v[i] = varasto;

              s.push_back({ 1, i+1 });

              // toinen vaihto
              varasto = v[x-1];
              v[x-1] = v[0];
              v[0] = varasto;

              s.push_back({ 1, x });

              // kolmas vaihto
              varasto = v[i];
              v[i] = v[0];
              v[0] = varasto;

              s.push_back({ i+1, 1 });
            }
          } else {
            int varasto = v[x-1];

            v[x-1] = x;
            v[i] = varasto;

            s.push_back({ i+1, x });
          }

          break;
        }
      }
    }

    x++;
    //for (int i : v) cout << i << " ";
    //cout << endl;
  } while (!isSorted());
}

bool isPossible() {
  if (n == 1) {
    return true;
  }

  if (n == 2) {
    if (v[0] == 1) return true;
    else return false;
  }

  if (n == 3) {
    if (v[1] == 2) return true;
    else return false;
  }

  if (n == 4) {
    if (v[1] != 2 && v[2] != 3) return false;
    else return true;
  }

  return true;
}

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

  cin >> t;

  for (int i = 0; i < t; i++) {
    cin >> n;
    v.clear();
    v.resize(n);
    for (int& i : v) cin >> i;

    if (isPossible()) {
      runSort();
      cout << s.size() << "\n";
      for (pair<int, int> p : s) cout << p.first << " " << p.second << "\n";
      //for (int i : v) cout << i << " ";
    } else {
      cout << "-1\n";
    }
  }
}

Test 1

Group: 1, 2

Verdict: WRONG ANSWER

Test 2

Group: 2

Verdict: WRONG ANSWER