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

• 問題: No.3510 RPS Eliminations
• ユーザー: 왕지후
• 提出日時: 2026-04-18 12:23:11
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 101 ms / 2,000 ms
• コード長: 7,469 bytes
• コンパイル時間: 2,503 ms
• コンパイル使用メモリ: 344,276 KB
• 実行使用メモリ: 32,564 KB
• 最終ジャッジ日時: 2026-04-18 12:23:18
• 合計ジャッジ時間: 6,761 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 28

ソースコード

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

using ull = unsigned long long;
static const ull INF = (ull)4e18;

static inline ull cap_add(ull a, ull b) {
    ull c = a + b;
    if (c < a || c > INF) return INF;
    return c;
}

static inline ull cap_mul(ull a, ull b) {
    __uint128_t z = (__uint128_t)a * (__uint128_t)b;
    if (z > INF) return INF;
    return (ull)z;
}

// 0:R, 1:P, 2:S
static inline int loseTo(int x) {
    // winner x beats loseTo(x)
    if (x == 0) return 2; // R beats S
    if (x == 1) return 0; // P beats R
    return 1;             // S beats P
}

static inline int winner(int a, int b) {
    if (a == b) return -1; // invalid
    return (loseTo(a) == b ? a : b);
}

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick() {}
    Fenwick(int n): n(n), bit(n + 1, 0) {}
    void add(int i, int v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    int kth(int k) const {
        int idx = 0;
        int pw = 1;
        while ((pw << 1) <= n) pw <<= 1;
        for (int d = pw; d; d >>= 1) {
            int ni = idx + d;
            if (ni <= n && bit[ni] < k) {
                idx = ni;
                k -= bit[ni];
            }
        }
        return idx + 1;
    }
};

struct Node {
    int l = -1, r = -1;
    int L = -1, R = -1; // leaf interval
    array<ull, 3> dp{0, 0, 0};
};

static inline array<ull, 3> pull(const array<ull, 3>& A, const array<ull, 3>& B) {
    array<ull, 3> res{0, 0, 0};
    for (int t = 0; t < 3; t++) {
        int z = loseTo(t);
        res[t] = cap_add(
            cap_mul(A[t], B[z]),
            cap_mul(A[z], B[t])
        );
    }
    return res;
}

// weighted total = sum_r w[r] * dp[u][r]
static inline ull weighted_total(const array<ull, 3>& w, const array<ull, 3>& dp) {
    ull ret = 0;
    for (int i = 0; i < 3; i++) ret = cap_add(ret, cap_mul(w[i], dp[i]));
    return ret;
}

// left subtree context weights
// cL[a] = number of completions (right subtree + outside) if left outcome is a
static inline array<ull, 3> left_ctx(const array<ull, 3>& w, const array<ull, 3>& dpR) {
    array<ull, 3> c{0, 0, 0};
    for (int t = 0; t < 3; t++) {
        int z = loseTo(t);
        // left outcome = t, right outcome = z -> parent t
        c[t] = cap_add(c[t], cap_mul(w[t], dpR[z]));
        // left outcome = z, right outcome = t -> parent t
        c[z] = cap_add(c[z], cap_mul(w[t], dpR[t]));
    }
    return c;
}

// right subtree context weights if left outcome is fixed to a
// dR[b] = number of completions (outside) if right outcome is b
static inline array<ull, 3> right_ctx(const array<ull, 3>& w, int a) {
    array<ull, 3> d{0, 0, 0};
    for (int t = 0; t < 3; t++) {
        int z = loseTo(t);
        if (a == t) {
            // need right = z
            d[z] = cap_add(d[z], w[t]);
        }
        if (a == z) {
            // need right = t
            d[t] = cap_add(d[t], w[t]);
        }
    }
    return d;
}

struct Frame {
    int u;
    array<ull, 3> w;
    ull K;
    int stage; // 0: enter, 1: after left, 2: after right
    int leftOutcome;
    ull leftResidual;
};

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

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

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

        vector<Node> tr(2 * N + 5);

        for (int i = 1; i <= N; i++) {
            tr[i].L = tr[i].R = i;
            tr[i].dp = {1, 1, 1}; // leaf can be R/P/S
        }

        // Build merge tree from A
        vector<int> rootAtPos(N + 1);
        for (int i = 1; i <= N; i++) rootAtPos[i] = i;

        Fenwick fw(N);
        for (int i = 1; i <= N; i++) fw.add(i, 1);

        int ptr = N;
        for (int i = 1; i <= N - 1; i++) {
            int k = A[i];
            int posL = fw.kth(k);
            int posR = fw.kth(k + 1);

            int x = rootAtPos[posL];
            int y = rootAtPos[posR];

            ++ptr;
            tr[ptr].l = x;
            tr[ptr].r = y;
            tr[ptr].L = tr[x].L;
            tr[ptr].R = tr[y].R;
            tr[ptr].dp = pull(tr[x].dp, tr[y].dp);

            rootAtPos[posL] = ptr;
            fw.add(posR, -1);
        }

        int onlyPos = fw.kth(1);
        int root = rootAtPos[onlyPos];

        auto solve_for_target = [&](int target) -> string {
            array<ull, 3> rootW{0, 0, 0};
            rootW[target] = 1;

            if (weighted_total(rootW, tr[root].dp) < K) return "-1";

            vector<char> ans(N + 1, '?');

            vector<Frame> st;
            st.reserve(2 * N + 5);
            st.push_back({root, rootW, K, 0, -1, 0});

            int retOutcome = -1;
            ull retResidual = 0;

            static const int order[3] = {1, 0, 2}; // P < R < S
            static const char chOf[3] = {'R', 'P', 'S'};

            while (!st.empty()) {
                Frame &f = st.back();
                int u = f.u;

                if (f.stage == 0) {
                    ull total = weighted_total(f.w, tr[u].dp);
                    if (total < f.K) {
                        return "-1";
                    }

                    if (tr[u].l == -1) {
                        // leaf
                        ull kcur = f.K;
                        bool ok = false;
                        for (int idx = 0; idx < 3; idx++) {
                            int c = order[idx];
                            ull cnt = f.w[c];
                            if (kcur > cnt) {
                                kcur -= cnt;
                            } else {
                                ans[tr[u].L] = chOf[c];
                                retOutcome = c;
                                retResidual = kcur; // rank inside this leaf choice block
                                ok = true;
                                break;
                            }
                        }
                        if (!ok) return "-1";
                        st.pop_back();
                        continue;
                    }

                    // go left first
                    array<ull, 3> cL = left_ctx(f.w, tr[tr[u].r].dp);
                    f.stage = 1;
                    st.push_back({tr[u].l, cL, f.K, 0, -1, 0});
                    continue;
                }

                if (f.stage == 1) {
                    // left child returned
                    f.leftOutcome = retOutcome;
                    f.leftResidual = retResidual;

                    array<ull, 3> dR = right_ctx(f.w, f.leftOutcome);
                    f.stage = 2;
                    st.push_back({tr[u].r, dR, f.leftResidual, 0, -1, 0});
                    continue;
                }

                // stage == 2
                {
                    int rightOutcome = retOutcome;
                    ull rightResidual = retResidual;

                    int w = winner(f.leftOutcome, rightOutcome);
                    if (w == -1) return "-1";

                    retOutcome = w;
                    retResidual = rightResidual;
                    st.pop_back();
                }
            }

            string res;
            res.reserve(N);
            for (int i = 1; i <= N; i++) res.push_back(ans[i]);
            return res;
        };

        cout << solve_for_target(0) << '\n'; // R
        cout << solve_for_target(1) << '\n'; // P
        cout << solve_for_target(2) << '\n'; // S
    }

    return 0;
}