AtCoder Regular Contest 162 - B. Insertion Sort 2 (1124)

B. Insertion Sort 2

해당 연산을 함으로써 불변인것을 생각한다.

인접한 두 개의 수를 이동시키는 것은 inversion counting의 parity를 변화시키지 못한다.

inversion이 짝수개만큼 변하기 때문이다.

인접한 두개가 이동하면서 교차되는 것들에 대해서 $a_i, a_{i+1}$ 는 항상 inversion을 $+1, -1$ 씩 변화시키므로 다른 하나와 크로스될 때마다 $-2, 0, +2$ 처럼 parity를 변화시키게 된다.

따라서 Inversion count가 처음에 홀수개라면 정답은 No 이다.

굳이 직접 검사해줄 필요 없이 construction의 결과로 정렬이 되지 않으면 No 라고 출력해주면 된다.

그렇지 않다면 항상 가능하다.

$1$부터 $1$이 가야할 자리에 안가있으면 그것이 있는 자리를 $k$라고 하면 $i=k$ 로 설정하고 $j=0$ 으로 설정해서 $1$을 제일 앞으로 보낼 수 있다.

어떨때는 그 다음 앞으로 보내주어야 할 수가 제일 뒤 $k=n$ 인 경우가 있는데, 이 경우엔 연산을 두 번 써서 보내줄 수 있다.

따라서 하나의 수를 적절한 위치로 보내는데 최대 $2$번의 연산이 필요하다.

이런식으로 모두 보내며 $1$부터 $n-2$ 까지만 시행한다.

$n-1$이나 $n$은 $n-2$ 까지 시행한 시점에서 자신의 자리에 가있지 않으면 그것을 올바르게 자리해줄 수 없기 때문이다.

void solve() {  
   int n;  
   cin >> n;  
   vi p(n + 1);  
   fv1(p);  
  
   vector<pi> ans;  
   auto get = [&](int i, int j) {  
      vi c{0};  
      for (int k = 1; k <= j; k++) c.pb(p[k]);  
      c.pb(p[i]);  
      c.pb(p[i + 1]);  
      for (int k = j + 1; k <= n; k++) if (k != i && k != i + 1)c.pb(p[k]);  
      return c;  
   };  
  
   for (int i = 1; i <= n - 2; i++) {  
      int idx = -1;  
      for (int j = 1; j <= n; j++) {  
         if (p[j] == i) {  
            idx = j;  
            break;  
         }  
      }  
      if (idx == i) continue;  
  
      if (idx == n) {  
         ans.pb({idx - 1, i - 1});  
         p = get(idx - 1, i - 1);  
         ans.pb({i + 1, i - 1});  
         p = get(i + 1, i - 1);  
      } else {  
         ans.pb({idx, i - 1});  
         p = get(idx, i - 1);  
      }  
   }  
   if (!is_sorted(all(p))) {  
      cout << "No";  
      return;  
   }  
   cout << "Yes\n" << sz(ans) << endl;  
   for (auto &[i, j]: ans) cout << i << ' ' << j << endl;  
}