結果

問題 No.3183 Swap or Rotate
コンテスト
ユーザー D M
提出日時 2025-09-18 10:18:28
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 986 bytes
コンパイル時間 2,847 ms
コンパイル使用メモリ 281,332 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-09-18 10:18:45
合計ジャッジ時間 4,358 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; 
  if(!(cin >> n)) return 0;
  vector<int> P(n);
  for (int i = 0; i < n; ++i) cin >> P[i];

  string ops;
  ops.reserve(20000);

  auto doS = [&](){
    swap(P[0], P[1]);
    ops.push_back('S');
  };
  auto doR = [&](){
    rotate(P.begin(), P.begin()+1, P.end()); // 左回転（Pi <- P(i+1)）
    ops.push_back('R');
  };

  // リング上のバブルソート：各ステップで (必要ならS) -> R を行う
  // n*(n-1) 回で循環的昇順（k,k+1,...,n-1,0,1,...,k-1）になる
  for (int t = 0; t < n*(n-1); ++t) {
    // ただし (n-1,0) の並びは崩さないようにする
    if (P[0] > P[1] && !(P[0] == n-1 && P[1] == 0)) doS();
    doR();
  }

  // 先頭を 0 にそろえる
  int pos0 = -1;
  for (int i = 0; i < n; ++i) if (P[i] == 0) { pos0 = i; break; }
  for (int i = 0; i < pos0; ++i) doR();

  cout << ops << '\n';
  return 0;
}
0