#1160271 (C++23) No.3510 RPS Eliminations

• 問題: No.3510 RPS Eliminations
• ユーザー: 쿠로에산
• 提出日時: 2026-04-19 01:35:58
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: MLE
• 実行時間: -
• コード長: 3,348 bytes
• コンパイル時間: 2,889 ms
• コンパイル使用メモリ: 347,332 KB
• 実行使用メモリ: 2,606,336 KB
• 最終ジャッジ日時: 2026-04-19 01:36:47
• 合計ジャッジ時間: 10,454 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_1

ファイルパターン	結果
sample	-- * 1
other	MLE * 2 -- * 26

ソースコード

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

using ll = long long;

static const ll ceiling = (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> current;
        current.reserve(2*N);

        for(int i=0;i<N;i++) current.push_back(i);

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

        int node_id = N;

        for(int i=0;i<N-1;i++){

            int pos = A[i]-1;

            int L = current[pos];
            int R = current[pos+1];

            left[node_id] = L;
            right[node_id] = R;

            current.erase(current.begin()+pos);
            current.insert(current.begin()+pos, node_id);

            node_id++;
        }

        int root = node_id - 1;

        auto decide = [&](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;
        };
         // why r u watching this!!!! cpctfたのしい
        function<void(int)> calc = [&](int v){

            if(v < N){
                dp[v] = {1,1,1};
                return;
            }

            calc(left[v]);
            calc(right[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 = decide(C[i], C[j]);
                    int id = (w=='R'?0:w=='P'?1:2);

                    res[id] += dp[left[v]][i] * dp[right[v]][j];

                    if(res[id] > ceiling) res[id] = ceiling;
                }
            }

            dp[v] = res;
        };

        calc(root);

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

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

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

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

                for(char pick : order){

                    ll ways = 0;

                    for(int i=0;i<3;i++){
                        for(int j=0;j<3;j++){

                            char w = decide("RPS"[i], "RPS"[j]);
                            int id = (w=='R'?0:w=='P'?1:2);

                            if(id == target)
                                ways += dp[left[v]][i] * dp[right[v]][j];
                        }
                    }

                    if(k > ways){
                        k -= ways;
                    } else {
                        return build(left[v],k) + build(right[v],k);
                    }
                }

                return "-1";
            };

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

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