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

• 問題: No.3510 RPS Eliminations
• ユーザー: gojoxd
• 提出日時: 2026-04-18 20:11:03
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 6,193 bytes
• コンパイル時間: 2,254 ms
• コンパイル使用メモリ: 179,380 KB
• 実行使用メモリ: 22,912 KB
• 最終ジャッジ日時: 2026-04-18 20:11:47
• 合計ジャッジ時間: 10,937 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

ファイルパターン	結果
sample	-- * 1
other	WA * 20 TLE * 1 -- * 7

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

const long long INF = 1000000000000000001LL;

inline long long add(long long a, long long b) { return min(INF, a + b); }
inline long long mul(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    if (INF / a < b) return INF;
    return min(INF, a * b);
}

// 0: P, 1: R, 2: S
int win_char(int a, int b) {
    if ((a == 0 && b == 1) || (a == 1 && b == 0)) return 0; // P beats R
    if ((a == 1 && b == 2) || (a == 2 && b == 1)) return 1; // R beats S
    if ((a == 2 && b == 0) || (a == 0 && b == 2)) return 2; // S beats P
    return -1; // Ties do not naturally occur in valid evaluations
}

const int MAXN = 200005;
int left_child[MAXN * 2], right_child[MAXN * 2], parent_node[MAXN * 2];
int sz[MAXN * 2];
bool has_right_ancestor[MAXN * 2];

long long pow2[MAXN];
int eval_c[MAXN * 2];
int jump[MAXN * 2];
int map_c[MAXN * 2][3];

struct Fenwick {
    int n;
    vector<int> tree;
    Fenwick(int n) : n(n), tree(n + 1, 0) {}
    void add(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    int find_kth(int k) {
        int idx = 0;
        for (int i = 1 << 18; i > 0; i >>= 1) {
            if (idx + i <= n && tree[idx + i] < k) {
                idx += i; k -= tree[idx];
            }
        }
        return idx + 1;
    }
};

void dfs(int u, bool has_right) {
    sz[u] = 1;
    has_right_ancestor[u] = has_right;
    if (left_child[u] == 0) return;
    dfs(left_child[u], has_right);
    dfs(right_child[u], true);
    sz[u] = sz[left_child[u]] + sz[right_child[u]];
}

void solve() {
    int N; long long K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 1; i < N; i++) cin >> A[i];

    if (K > pow2[N - 1]) {
        cout << "-1\n-1\n-1\n";
        return;
    }

    Fenwick fenw(N);
    vector<int> node_at(N + 1);
    for (int i = 1; i <= N; i++) {
        fenw.add(i, 1); node_at[i] = i;
        left_child[i] = right_child[i] = parent_node[i] = 0;
    }

    for (int i = 1; i < N; i++) {
        int p1 = fenw.find_kth(A[i]), p2 = fenw.find_kth(A[i] + 1);
        int u = node_at[p1], v = node_at[p2];
        int idx = N + i;
        left_child[idx] = u; right_child[idx] = v;
        parent_node[u] = parent_node[v] = idx;
        node_at[p1] = idx; fenw.add(p2, -1);
    }
    
    int root = 2 * N - 1;
    parent_node[root] = 0;
    dfs(root, false);

    int target_order[3] = {1, 0, 2}; // R, P, S

    for (int i = 0; i < 3; i++) {
        int target = target_order[i];
        for (int j = 1; j <= 2 * N - 1; j++) eval_c[j] = -1;
        
        long long current_k = K;
        string ans = "";
        
        for (int leaf = 1; leaf <= N; leaf++) {
            int chosen_c = -1;
            
            for (int c = 0; c < 3; ++c) {
                long long dp[3] = {0, 0, 0};
                dp[c] = 1;
                int curr = leaf;
                
                while (curr != root) {
                    int p = parent_node[curr];
                    if (curr == left_child[p]) {
                        int R = right_child[p];
                        long long W = pow2[sz[R] - 1];
                        long long nxt[3];
                        nxt[0] = min(INF, W * (dp[0] + dp[2]));
                        nxt[1] = min(INF, W * (dp[0] + dp[1]));
                        nxt[2] = min(INF, W * (dp[1] + dp[2]));
                        dp[0] = nxt[0]; dp[1] = nxt[1]; dp[2] = nxt[2];
                        curr = p;
                        
                        // Extremely aggressive early break: 
                        // If path saturates to INF and no right-steps remain to cancel it out
                        if (dp[0] == INF && dp[1] == INF && dp[2] == INF && !has_right_ancestor[curr]) break;
                        
                    } else {
                        // O(1) Fast-forward over fully evaluated subtrees
                        int top = jump[curr];
                        long long nxt[3] = {0, 0, 0};
                        for (int x = 0; x < 3; ++x) {
                            if (dp[x] > 0) {
                                int res = map_c[curr][x];
                                if (res != -1) nxt[res] = add(nxt[res], dp[x]);
                            }
                        }
                        dp[0] = nxt[0]; dp[1] = nxt[1]; dp[2] = nxt[2];
                        curr = top;
                    }
                }
                
                long long ways = dp[target];
                if (ways >= current_k) {
                    chosen_c = c;
                    break;
                } else {
                    current_k -= ways;
                }
            }
            
            ans += (chosen_c == 0 ? 'P' : (chosen_c == 1 ? 'R' : 'S'));
            
            // Systematically lock evaluated paths & Build jump pointers dynamically
            eval_c[leaf] = chosen_c;
            int curr = leaf;
            while (curr != root) {
                int p = parent_node[curr];
                if (curr == right_child[p]) {
                    int L = left_child[p];
                    eval_c[p] = win_char(eval_c[L], eval_c[curr]);
                    curr = p;
                } else {
                    break;
                }
            }
            
            if (curr != root) {
                int p = parent_node[curr];
                int R = right_child[p];
                if (parent_node[p] != 0 && p == right_child[parent_node[p]]) {
                    jump[R] = jump[p];
                    for (int x = 0; x < 3; ++x) map_c[R][x] = map_c[p][win_char(eval_c[curr], x)];
                } else {
                    jump[R] = p;
                    for (int x = 0; x < 3; ++x) map_c[R][x] = win_char(eval_c[curr], x);
                }
            }
        }
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    pow2[0] = 1;
    for (int i = 1; i < MAXN; i++) pow2[i] = min(INF, pow2[i - 1] * 2);
    
    int t;
    if (cin >> t) while (t--) solve();
    return 0;
}