結果

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

ソースコード

diff #
raw source code 

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

using ll = long long;

static const ll INF = (ll)4e18;

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

    int T; cin >> T;

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

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

        vector<int> L(2*N+5,-1), R(2*N+5,-1);
        vector<array<ll,3>> dp(2*N+5);

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

        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.erase(cur.begin()+p);
            cur.insert(cur.begin()+p,id);

            id++;
        }
        // why r u watching this!!!! cpctfたのしい
        int root = id-1;

        auto 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;
        };

        function<void(int)> dfs = [&](int v){
            if(v < N){
                dp[v]={1,1,1};
                return;
            }

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

            array<ll,3> res={0,0,0};
            char C[3]={'R','P','S'};

            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);

                    res[t]+=dp[L[v]][i]*dp[R[v]][j];
                    if(res[t]>INF) res[t]=INF;
                }
            }

            dp[v]=res;
        };

        dfs(root);

        auto solve = [&](int target)->string{

            function<string(int,ll)> go = [&](int v,ll k)->string{

                if(v < N){
                    string s="RPS";
                    for(char c:s){
                        if(k==1) return string(1,c);
                        k--;
                    }
                }

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

                for(char c:ord){
                    ll cnt=0;

                    for(int i=0;i<3;i++){
                        for(int j=0;j<3;j++){
                            char w=win("RPS"[i],"RPS"[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 go(L[v],k)+go(R[v],k);
                }

                return "-1";
            };

            if(dp[root][target]<K) return "-1";
            return go(root,K);
        };

        for(int i=0;i<3;i++)
            cout<<solve(i)<<"\n";
    }
}
0