[ARC162] B - Insertion Sort 2

[Q] https://atcoder.jp/contests/arc162/tasks/arc162_b

考察
・要素数が1000で、2000回のswapまで許される。
・先頭から1,2,3,….とそろえていけば1000回の操作で達成できそう。
・2 3 4 1 の場合を考える。"1"を先頭にもっていきたいけど、要素の末端にあるときは、
-> 2 3 [4 1] を1つ後ろにずらして、
-> 2 [4 1] 3を経由して
-> [1 3] 2 4と変形させる必要がある。2手使うことになる。
・最悪の場合でも2*1000の2000手で達成できることがわかる。
・頑張って実装する

実装

int main() {
  ll N;
  cin >> N;
  vector<ll> P(N);   // P[index]=値
  vector<ll> pos(N); // pos[値]=index
  rep(i, N){
    cin >> P[i];
    --P[i];
    pos[P[i]] = i;
  }
 
  ll target = 0;
  vector<pll> ans;

  auto move=[&](ll s)->bool{
    if (s == N - 1){// 2 3 1のとき
      if (s - target < 2) return true; // No
      ans.emplace_back(s - 1, s - 2);
      // 末端の要素を1つ左にずらす
      rotate(P.begin() + s - 2, P.begin() + s - 1, P.end());
      for(ll t = N - 3; t < N; ++t){
        pos[P[t]] = t;
      }
      --s;
    }
    ans.emplace_back(s, target);
    // 2要素スライド
    rotate(P.begin() + target, P.begin() + s, P.begin() + s + 2);
    for(ll t = target; t < s + 2; ++t){
      pos[P[t]] = t;
    }
    return false;
  };

  while(1){
    while(target < N && P[target] == target) ++target;
    if (target >= N) break; // 昇順になった
    if(move(pos[target])){
      cout << "No" << endl;
      return 0;
    }
  }

  cout << "Yes" << endl;
  cout << ans.size() << endl;
  rep(i, ans.size()){
    cout << ans[i].first + 1 << " " << ans[i].second << " \n"[i == (ans.size() - 1)];
  }
}

https://atcoder.jp/contests/arc162/submissions/42724828