結果

問題 No.3183 Swap or Rotate
ユーザー srjywrdnprkt
提出日時 2025-07-25 16:41:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 1,000 ms
コード長 1,382 bytes
コンパイル時間 3,301 ms
コンパイル使用メモリ 279,008 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-07-25 16:41:50
合計ジャッジ時間 4,815 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

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

    /*
       (i,i+1)を交換する
       0 1 2 3
       3 1 0 2
       i回RしてからS

       0 3 1 2

       (1,2) 3 0 1 2
       (0,1) 0 3 1 2
       (1,2) 0 1 3 2
       (2,3) 0 1 2 3
       転倒数の分だけSをしないといけない。

       最悪ケース
       3 2 1 0
       (2,3) 3 2 0 1
       (1,2) 3 0 2 1
       (0,1) 0 3 2 1
       (2,3) 0 3 1 2
       (1,2) 0 1 3 2
       (2,3) 0 1 2 3

       逆向きにすれば？
       (0,1) 2 3 1 0
       (1,2) 2 1 3 0
       (2,3) 2 1 0 3
       (0,1) 1 2 0 3
       (1,2) 1 0 2 3
       (0,1) 0 1 2 3

       iをi番目に持っていくためには
       最大でN回の置換+N回の回転が必要。
       N*N*2=20000以下
     */

    int N, now=0;
    cin >> N;
    vector<int> p(N);
    
    for (int i=0; i<N; i++){
        cin >> p[i];
    }

    string S="";
    for (int i=N-1; i>=0; i--){
        while (p[now] != i){
            now = (now+1) % N;
            S += "R";
        }
        while (p[i] != i){
            S += "SR";
            swap(p[now], p[(now+1)%N]);
            now = (now+1) % N;
        }
    }
    cout << S << endl;

    return 0;
}
0