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

• 問題: No.3510 RPS Eliminations
• ユーザー: e032_Ashmit_Rana
• 提出日時: 2026-04-18 03:02:16
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 78 ms / 2,000 ms
• コード長: 5,076 bytes
• コンパイル時間: 2,490 ms
• コンパイル使用メモリ: 346,408 KB
• 実行使用メモリ: 20,776 KB
• 最終ジャッジ日時: 2026-04-18 03:02:24
• 合計ジャッジ時間: 7,412 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

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

ソースコード

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

using int64 = long long;

static constexpr int64 INF = 1000000000000000000LL;

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

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

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

    explicit Fenwick(int n_ = 0) { init(n_); }

    void init(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }

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

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

struct Node {
    int left = -1;
    int right = -1;
};

struct Frame {
    int node = 0;
    array<int64, 3> weight{};
    int64 k = 0;
    int phase = 0;
    int left_state = -1;
};

// State ids follow lexicographic order: P < R < S.
static constexpr char HAND[3] = {'P', 'R', 'S'};

int prey(int x) {
    // P beats R, R beats S, S beats P.
    return (x + 1) % 3;
}

int predator(int x) {
    return (x + 2) % 3;
}

string kth_string(const vector<Node>& nodes, const vector<int64>& cnt, int root,
                  array<int64, 3> root_weight, int64 k, int n) {
    string answer;
    answer.reserve(n);

    vector<Frame> stack;
    stack.reserve(nodes.size() * 2);
    stack.push_back({root, root_weight, k, 0, -1});

    int last_state = -1;
    int64 last_rep = 0;

    while (!stack.empty()) {
        Frame cur = stack.back();
        stack.pop_back();

        const Node& node = nodes[cur.node];
        if (cur.phase == 0) {
            if (node.left == -1) {
                for (int s = 0; s < 3; ++s) {
                    int64 block = cur.weight[s];
                    if (cur.k > block) {
                        cur.k -= block;
                    } else {
                        answer.push_back(HAND[s]);
                        last_state = s;
                        last_rep = cur.k;
                        break;
                    }
                }
                continue;
            }

            array<int64, 3> left_weight{};
            int64 right_count = cnt[node.right];
            for (int y = 0; y < 3; ++y) {
                int64 suffix_sum = cap_add(cur.weight[y], cur.weight[predator(y)]);
                left_weight[y] = cap_mul(right_count, suffix_sum);
            }

            stack.push_back({cur.node, cur.weight, cur.k, 1, -1});
            stack.push_back({node.left, left_weight, cur.k, 0, -1});
        } else if (cur.phase == 1) {
            int y = last_state;
            int64 suffix_rank = last_rep;

            array<int64, 3> right_weight{};
            right_weight[prey(y)] = cap_add(right_weight[prey(y)], cur.weight[y]);
            right_weight[predator(y)] =
                cap_add(right_weight[predator(y)], cur.weight[predator(y)]);

            stack.push_back({cur.node, cur.weight, 0, 2, y});
            stack.push_back({node.right, right_weight, suffix_rank, 0, -1});
        } else {
            int left_state = cur.left_state;
            int right_state = last_state;
            last_state = (right_state == prey(left_state) ? left_state : right_state);
        }
    }

    return answer;
}

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

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

        vector<Node> nodes;
        vector<int64> cnt;
        nodes.reserve(2 * N - 1);
        cnt.reserve(2 * N - 1);

        vector<int> at(N + 1);
        for (int i = 1; i <= N; ++i) {
            at[i] = static_cast<int>(nodes.size());
            nodes.push_back({-1, -1});
            cnt.push_back(1);
        }

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

        for (int i = 1; i <= N - 1; ++i) {
            int a;
            cin >> a;
            int pos_l = fw.kth(a);
            int pos_r = fw.kth(a + 1);
            int left = at[pos_l];
            int right = at[pos_r];

            int parent = static_cast<int>(nodes.size());
            nodes.push_back({left, right});
            cnt.push_back(cap_mul(2, cap_mul(cnt[left], cnt[right])));

            at[pos_l] = parent;
            fw.add(pos_r, -1);
        }

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

        // Requested order is R, P, S. Internal ids are P=0, R=1, S=2.
        for (int target : {1, 0, 2}) {
            if (K > cnt[root]) {
                cout << -1 << '\n';
                continue;
            }
            array<int64, 3> weight{};
            weight[target] = 1;
            cout << kth_string(nodes, cnt, root, weight, K, N) << '\n';
        }
    }

    return 0;
}