#1158856 (C++17) No.3510 RPS Eliminations

• 問題: No.3510 RPS Eliminations
• ユーザー: e032_Ashmit_Rana
• 提出日時: 2026-04-18 01:40:10
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,259 bytes
• コンパイル時間: 1,455 ms
• コンパイル使用メモリ: 223,776 KB
• 実行使用メモリ: 20,808 KB
• 最終ジャッジ日時: 2026-04-18 01:40:23
• 合計ジャッジ時間: 5,915 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	WA * 1
other	WA * 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 nxt = idx + step;
            if (nxt <= n && bit[nxt] < k) {
                idx = nxt;
                k -= bit[nxt];
            }
        }
        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;
};

// Symbol ids are in 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> st;
    st.reserve(nodes.size() * 2);
    st.push_back({root, root_weight, k, 0, -1});

    int last_state = -1;
    int64 last_rep = 0;

    while (!st.empty()) {
        Frame f = st.back();
        st.pop_back();

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

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

            st.push_back({f.node, f.weight, f.k, 1, -1});
            st.push_back({cur.left, left_weight, f.k, 0, -1});
        } else if (f.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)], f.weight[y]);
            right_weight[predator(y)] =
                cap_add(right_weight[predator(y)], f.weight[predator(y)]);

            st.push_back({f.node, f.weight, 0, 2, y});
            st.push_back({cur.right, right_weight, suffix_rank, 0, -1});
        } else {
            int y = f.left_state;
            int z = last_state;
            if (z == prey(y)) {
                last_state = y;
            } else {
                last_state = z;
            }
            // last_rep is already the copy index belonging to the selected parent 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] = (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);

        int root = 0;
        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 = (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);
            root = parent;
        }

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

        // Required final hands are R, P, S.
        int targets[3] = {1, 0, 2};
        for (int qi = 0; qi < 3; ++qi) {
            if (qi) cout << ' ';
            int target = targets[qi];
            if (K > cnt[root]) {
                cout << -1;
            } else {
                array<int64, 3> w{};
                w[target] = 1;
                cout << kth_string(nodes, cnt, root, w, K, N);
            }
        }
        cout << '\n';
    }

    return 0;
}