結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー 쿠로에산
提出日時 2026-04-19 01:55:06
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,569 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,985 ms
コンパイル使用メモリ 340,640 KB
実行使用メモリ 32,012 KB
最終ジャッジ日時 2026-04-19 01:56:46
合計ジャッジ時間 9,075 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;
static const ll INF = (ll)4e18;

int N;
ll K;

int L[400005], R[400005];
ll dp[400005][3];

char C[3] = {'R','P','S'};

inline int win(int a,int b){
    if(a==b) return a;
    if(a==0 && b==2) return 0;
    if(a==2 && b==1) return 2;
    return 1;
}

void dfs(int v){
    if(L[v]==-1){
        for(int i=0;i<3;i++) dp[v][i]=1;
        return;
    }

    dfs(L[v]);
    dfs(R[v]);

    for(int i=0;i<3;i++) dp[v][i]=0;

    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            int t = win(i,j);
            __int128 add = (__int128)dp[L[v]][i] * dp[R[v]][j];
            if(add > INF) add = INF;
            dp[v][t] = min(INF, dp[v][t] + (ll)add);
        }
    }
}

string build(int v, ll &k, int target){
    if(L[v]==-1){
        for(int i=0;i<3;i++){
            if(i==target){
                if(k==1) return string(1,C[i]);
                k--;
            }
        }
        return "-1";
    }

    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            int t = win(i,j);
            if(t != target) continue;

            ll ways = min(INF, dp[L[v]][i] * dp[R[v]][j]);

            if(k > ways){
                k -= ways;
            }else{
                string a = build(L[v], k, i);
                if(a=="-1") return "-1";

                string b = build(R[v], k, j);
                if(b=="-1") return "-1";

                return string(1,C[target]) + a + b;
            }
        }
    }
    return "-1";
}

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

    int T;
    cin >> T;

    while(T--){
        cin >> N >> K;
        vector<int> A(N-1);
        for(int i=0;i<N-1;i++) cin >> A[i];

        for(int i=0;i<400005;i++){
            L[i]=R[i]=-1;
            for(int j=0;j<3;j++) dp[i][j]=0;
        }

        vector<int> cur(N);
        iota(cur.begin(), cur.end(), 0);

        int ptr = N;

        for(int i=0;i<N-1;i++){
            int p = A[i]-1;

            int u = cur[p];
            int v = cur[p+1];

            L[ptr]=u;
            R[ptr]=v;

            cur[p]=ptr;
            cur.erase(cur.begin()+p+1);

            ptr++;
        }

        int root = ptr-1;

        dfs(root);

        for(int t=0;t<3;t++){
            ll kk = K;
            string res = build(root, kk, t);

            if(res=="-1" || kk>0) cout << "-1\n";
            else cout << res << "\n";
        }
    }
}
0