Submission #34615935

---

Source Code Expand

// Author: Ruhan Habib (ruhanhabib39@gmail.com)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

vector<pair<char, int>> res;

void even_swaps (vector<int>& P, int i, int j) {
   int dx = i < j ? +2 : -2;
   for (; i != j; i += dx) {
      swap(P[i], P[i+dx]);
      res.emplace_back('B', min(i, i + dx));
   }
}

void odd_swaps (vector<int>& P, int i, int j) {
   int dx = i < j ? +1 : -1;
   for (; i != j; i += dx) {
      swap(P[i], P[i+dx]);
      res.emplace_back('A', min(i, i + dx));
   }
}

void work (int N, vector<int>& P) {
   vector<int> pos(N);
   for (int k = 0; k < N; k++) {
      pos[P[k]] = k;
   }

   int j = 0;
   while (j < N && (pos[j] - j) % 2 == 0) j++;

   if (j == N) {
      j = 0;
      while (j < N && pos[j] == j) j++;
      
      if (j == N) {
         assert (is_sorted(P.begin(), P.end()));
         return;
      }
   }


   int i = pos[j]; // i -> j

   if ((i - j) % 2 == 0) {
      even_swaps(P, i, j);
   } else {
      int y = (i & 1) ^ 1;
      while (y < N && (P[y] - y) % 2 == 0) y += 2;

      assert (y < N);

      int x = y == N - 1 ? y - 1 : y + 1;

      even_swaps(P, i, x);
      odd_swaps(P, x, y);
      even_swaps(P, y, j);
   }

   assert (res.size() <= 100 * 1000);

   work(N, P);
}

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

   int N; cin >> N;
   vector<int> P(N);
   for (int& x : P) {
      cin >> x;
      x--;
   }

   work(N, P);

   assert (res.size() <= 100 * 1000);

   cout << res.size() << "\n";

   for (auto [c, i] : res) {
      cout << c << " " << i+1 << "\n";
   }
}

Submission Info

Judge Result