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

• 問題: No.3510 RPS Eliminations
• ユーザー: sient
• 提出日時: 2026-04-19 00:44:15
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 98 ms / 2,000 ms
• コード長: 5,495 bytes
• コンパイル時間: 2,808 ms
• コンパイル使用メモリ: 343,976 KB
• 実行使用メモリ: 30,876 KB
• 最終ジャッジ日時: 2026-04-19 00:44:30
• 合計ジャッジ時間: 7,050 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

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

using int64 = long long;

static const int64 INF = (int64)4e18;

static int64 add_cap(int64 a, int64 b) {
    if (a >= INF || b >= INF) return INF;
    if (a > INF - b) return INF;
    return a + b;
}

static int64 mul_cap(int64 a, int64 b) {
    if (a == 0 || b == 0) return 0;
    if (a >= INF || b >= INF) return INF;
    if (a > INF / b) return INF;
    return a * b;
}

static int winner(int a, int b) {
    if (a == b) return -1;
    return ((a + 2) % 3 == b) ? a : b;
}

static char code_to_char(int c) {
    if (c == 0) return 'R';
    if (c == 1) return 'P';
    return 'S';
}

struct Fenwick {
    int n;
    vector<int> bit;

    Fenwick() : n(0) {}
    explicit Fenwick(int n_) : n(n_), bit(n_ + 1, 0) {}

    void add(int idx, int val) {
        for (int i = idx; i <= n; i += i & -i) bit[i] += val;
    }

    int kth(int k) const {
        int idx = 0;
        int step = 1;
        while ((step << 1) <= n) step <<= 1;
        for (int pw = step; pw > 0; pw >>= 1) {
            int nxt = idx + pw;
            if (nxt <= n && bit[nxt] < k) {
                idx = nxt;
                k -= bit[nxt];
            }
        }
        return idx + 1;
    }
};

static array<int64, 3> make_zero_weights() {
    return {0, 0, 0};
}

static string kth_string(
    int root,
    int leaves,
    const vector<int>& lc,
    const vector<int>& rc,
    const vector<array<int64, 3>>& cnt,
    array<int64, 3> root_w,
    int64 K
) {
    static const int lex_order[3] = {1, 0, 2};

    struct Frame {
        int node;
        array<int64, 3> w;
        int64 k;
        int stage;
        int left_res;
        int64 left_k;
    };

    vector<Frame> st;
    st.reserve(2 * leaves);
    st.push_back({root, root_w, K, 0, -1, 0});

    string ans(leaves, '?');
    int ret_res = -1;
    int64 ret_k = 0;

    while (!st.empty()) {
        Frame& cur = st.back();

        if (cur.node <= leaves) {
            int64 k = cur.k;
            int chosen = -1;
            for (int t = 0; t < 3; t++) {
                int c = lex_order[t];
                if (k > cur.w[c]) {
                    k -= cur.w[c];
                } else {
                    chosen = c;
                    break;
                }
            }

            ans[cur.node - 1] = code_to_char(chosen);
            ret_res = chosen;
            ret_k = k;
            st.pop_back();
            continue;
        }

        if (cur.stage == 0) {
            array<int64, 3> left_w = make_zero_weights();
            int right = rc[cur.node];
            for (int a = 0; a < 3; a++) {
                for (int b = 0; b < 3; b++) {
                    if (a == b) continue;
                    int w = winner(a, b);
                    left_w[a] = add_cap(left_w[a], mul_cap(cnt[right][b], cur.w[w]));
                }
            }

            cur.stage = 1;
            st.push_back({lc[cur.node], left_w, cur.k, 0, -1, 0});
            continue;
        }

        if (cur.stage == 1) {
            cur.left_res = ret_res;
            cur.left_k = ret_k;

            array<int64, 3> right_w = make_zero_weights();
            for (int b = 0; b < 3; b++) {
                if (b == cur.left_res) continue;
                int w = winner(cur.left_res, b);
                right_w[b] = cur.w[w];
            }

            cur.stage = 2;
            st.push_back({rc[cur.node], right_w, cur.left_k, 0, -1, 0});
            continue;
        }

        ret_res = winner(cur.left_res, ret_res);
        st.pop_back();
    }

    return ans;
}

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

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

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

        vector<int> lc(2 * N), rc(2 * N);
        vector<int> cur_node(N + 1), prv(N + 1), nxt(N + 1);
        Fenwick fw(N);

        for (int i = 1; i <= N; i++) {
            cur_node[i] = i;
            prv[i] = i - 1;
            nxt[i] = (i == N ? 0 : i + 1);
            fw.add(i, 1);
        }

        int tot = N;
        for (int step = 1; step < N; step++) {
            int left_pos = fw.kth(A[step]);
            int right_pos = nxt[left_pos];

            ++tot;
            lc[tot] = cur_node[left_pos];
            rc[tot] = cur_node[right_pos];
            cur_node[left_pos] = tot;

            fw.add(right_pos, -1);
            nxt[left_pos] = nxt[right_pos];
            if (nxt[right_pos] != 0) {
                prv[nxt[right_pos]] = left_pos;
            }
        }

        int root = tot;
        vector<array<int64, 3>> cnt(2 * N);
        for (int i = 1; i <= N; i++) {
            cnt[i] = {1, 1, 1};
        }
        for (int v = N + 1; v <= tot; v++) {
            cnt[v] = make_zero_weights();
            for (int c = 0; c < 3; c++) {
                int lose = (c + 2) % 3;
                cnt[v][c] = add_cap(
                    mul_cap(cnt[lc[v]][c], cnt[rc[v]][lose]),
                    mul_cap(cnt[lc[v]][lose], cnt[rc[v]][c])
                );
            }
        }

        for (int target = 0; target < 3; target++) {
            if (cnt[root][target] < K) {
                cout << -1 << '\n';
                continue;
            }
            array<int64, 3> root_w = make_zero_weights();
            root_w[target] = 1;
            cout << kth_string(root, N, lc, rc, cnt, root_w, K) << '\n';
        }
    }

    return 0;
}