結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー e032_Ashmit_Rana
提出日時 2026-04-18 01:45:59
言語 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,595 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,563 ms
コンパイル使用メモリ 343,472 KB
実行使用メモリ 17,680 KB
最終ジャッジ日時 2026-04-18 01:46:31
合計ジャッジ時間 29,933 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;
const ll INF = (ll)1e18;

struct Node {
    int left = -1, right = -1;
    ll cnt[3]; // 0=R,1=P,2=S
};

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<Node> nodes;
        nodes.reserve(2 * N);

        // create leaves
        vector<int> cur;
        for (int i = 0; i < N; i++) {
            Node nd;
            nd.cnt[0] = nd.cnt[1] = nd.cnt[2] = 1;
            nodes.push_back(nd);
            cur.push_back((int)nodes.size() - 1);
        }

        // build tree
        for (int i = 0; i < N - 1; i++) {
            int pos = A[i] - 1;

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

            Node nd;
            nd.left = L;
            nd.right = R;

            // R = (R,S), P = (P,R), S = (S,P)
            nd.cnt[0] = min(INF, nodes[L].cnt[0] * nodes[R].cnt[2]);
            nd.cnt[1] = min(INF, nodes[L].cnt[1] * nodes[R].cnt[0]);
            nd.cnt[2] = min(INF, nodes[L].cnt[2] * nodes[R].cnt[1]);

            nodes.push_back(nd);
            int id = (int)nodes.size() - 1;

            // replace in sequence
            cur.erase(cur.begin() + pos, cur.begin() + pos + 2);
            cur.insert(cur.begin() + pos, id);
        }

        int root = cur[0];

        function<string(int,int,ll)> build = [&](int u, int target, ll k) -> string {
            if (nodes[u].left == -1) {
                if (target == 0) return "R";
                if (target == 1) return "P";
                return "S";
            }

            int L = nodes[u].left;
            int R = nodes[u].right;

            int needL, needR;
            if (target == 0) { // R
                needL = 0; needR = 2;
            } else if (target == 1) { // P
                needL = 1; needR = 0;
            } else { // S
                needL = 2; needR = 1;
            }

            ll rightCnt = nodes[R].cnt[needR];
            rightCnt = min(rightCnt, INF);

            ll leftIdx = (k - 1) / rightCnt + 1;
            ll rightIdx = (k - 1) % rightCnt + 1;

            return build(L, needL, leftIdx) + build(R, needR, rightIdx);
        };

        for (int t = 0; t < 3; t++) {
            if (nodes[root].cnt[t] < K) {
                cout << -1 << '\n';
            } else {
                cout << build(root, t, K) << '\n';
            }
        }
    }

    return 0;
}
0