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 saveSwap(int a, int b) {
  if (!s.size()) {
    s.push_back({ a, b });
    return;
  }

  pair<int, int> last = s[s.size()-1];
  if (
      (last.first == a && last.second == b) ||
      (last.second == a && last.first == b)
    ) {
      s.pop_back();
    } else {
      s.push_back({ a, b });
    }
}

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});
              saveSwap(n, i+1);
 
              // toinen vaihto
              varasto = v[x-1];
              v[x-1] = v[n-1];
              v[n-1] = varasto;
 
              //s.push_back({ n, x });
              saveSwap(n, x);
 
              // kolmas vaihto
              varasto = v[i];
              v[i] = v[n-1];
              v[n-1] = varasto;
 
              //s.push_back({ n, i+1 });
              saveSwap(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 });
              saveSwap(1, i+1);
 
              // toinen vaihto
              varasto = v[x-1];
              v[x-1] = v[0];
              v[0] = varasto;
 
              //s.push_back({ 1, x });
              saveSwap(1, x);
 
              // kolmas vaihto
              varasto = v[i];
              v[i] = v[0];
              v[0] = varasto;
 
              //s.push_back({ i+1, 1 });
              saveSwap(i+1, 1);
            }
          } else {
            int varasto = v[x-1];
 
            v[x-1] = x;
            v[i] = varasto;
 
            //s.push_back({ i+1, x });
            saveSwap(i+1, x);
          }
          //for (int i : v) cout << i << " ";
          //cout << endl;
 
          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();
      if ((int)s.size() > n*5) {
        cout << "-1\n";
      } else {
        cout << s.size() << "\n";
        for (pair<int, int> p : s) {
          if (p.first > p.second) {
            cout << p.second << " " << p.first << "\n";
          } else {
            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: ACCEPTED