結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー 쿠로에산
提出日時 2026-04-19 01:47:33
言語 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
結果
WA  
実行時間 -
コード長 2,469 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,467 ms
コンパイル使用メモリ 335,808 KB
実行使用メモリ 28,672 KB
最終ジャッジ日時 2026-04-19 01:48:26
合計ジャッジ時間 21,326 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;

static const ll INF = (ll)4e18;

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

int cur[200005];

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

inline char win(char a,char b){
    if(a==b) return a;
    if(a=='R'&&b=='S') return 'R';
    if(a=='S'&&b=='P') return 'S';
    if(a=='P'&&b=='R') return 'P';
    return b;
}

void dfs(int v,int N){
    if(v < N){
        dp[v][0]=dp[v][1]=dp[v][2]=1;
        return;
    }
// MLEこんななる？これで1GB超えるはないでしょ。むずいって
    dfs(L[v],N);
    dfs(R[v],N);

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

    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            char w = win(C[i],C[j]);
            int t = (w=='R'?0:w=='P'?1:2);

            ll add = dp[L[v]][i] * dp[R[v]][j];
            dp[v][t] += add;

            if(dp[v][t] > INF) dp[v][t] = INF;
        }
    }
}

string build(int v,int N,ll &k,int target){
    if(v < N){
        for(char c : C){
            if(k==1) return string(1,c);
            k--;
        }
    }

    for(char pick : C){
        ll cnt = 0;

        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                char w = win(C[i],C[j]);
                int t = (w=='R'?0:w=='P'?1:2);

                if(t == target)
                    cnt += dp[L[v]][i] * dp[R[v]][j];
            }
        }

        if(k > cnt) k -= cnt;
        else return build(L[v],N,k,target) + build(R[v],N,k,target);
    }

    return "-1";
}
//vscode楽やね
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while(T--){
        int N;
        ll K;
        cin >> N >> K;

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

        for(int i=0;i<N;i++) cur[i]=i;

        int id=N;

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

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

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

            cur[p]=id;

            for(int j=p+1;j<N-(i+1);j++)
                cur[j]=cur[j+1];

            id++;
        }
//疲れた
        int root=id-1;

        dfs(root,N);

        for(int t=0;t<3;t++){
            if(dp[root][t] < K){
                cout << "-1\n";
                continue;
            }

            ll kk=K;
            cout << build(root,N,kk,t) << "\n";
        }
    }
}
0