#1160051 (C++23) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: gojoxd
• 提出日時: 2026-04-18 20:39:14
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,213 bytes
• コンパイル時間: 1,285 ms
• コンパイル使用メモリ: 178,876 KB
• 実行使用メモリ: 32,896 KB
• 最終ジャッジ日時: 2026-04-18 20:40:04
• 合計ジャッジ時間: 11,193 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

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

ソースコード

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

using namespace std;

// 10^18 + 1 to prevent overflow while accurately bounding K targets
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);
}

const int MAXN = 200005;
int left_child[MAXN * 2], right_child[MAXN * 2];
int sz[MAXN * 2];
long long pow2[MAXN * 2];

long long node_req[MAXN * 2][3];
int eval_ans[MAXN * 2];
int state[MAXN * 2];
int u_stack[MAXN * 2];

// Fenwick tree to track active elements and cleanly build the evaluation tree
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 solve() {
    int N; long long K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 1; i < N; i++) cin >> A[i];

    // Immediate bounds check. There are exactly 2^(N-1) combinations per target.
    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] = 0;
        sz[i] = 1; // Base case for sizes
    }

    // Build the evaluation tree
    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;
        node_at[p1] = idx; fenw.add(p2, -1);
        
        // Iterative Topological Size Evaluation (Bypasses recursive DFS)
        sz[idx] = sz[u] + sz[v];
    }
    
    int root = 2 * N - 1;

    // Requested alphabetical output order: R, P, S -> mapped to 1, 0, 2
    int target_order[3] = {1, 0, 2}; 

    for (int i = 0; i < 3; i++) {
        int target = target_order[i];
        long long K_global = K;
        
        string ans = "";
        ans.reserve(N); // Prevent dynamic reallocation overhead
        
        node_req[root][0] = node_req[root][1] = node_req[root][2] = 0;
        node_req[root][target] = 1; // Force the root character requirement
        
        int top = 0;
        u_stack[++top] = root;
        state[root] = 0;
        
        // Flat, Iterative DFS State Machine (Absolutely immune to Stack Overflow)
        while (top > 0) {
            int u = u_stack[top];
            
            // Leaf Processing
            if (u <= N) {
                int eval = -1;
                for (int c = 0; c < 3; ++c) {
                    if (node_req[u][c] >= K_global) {
                        ans += (c == 0 ? 'P' : (c == 1 ? 'R' : 'S'));
                        eval = c;
                        break;
                    } else {
                        K_global -= node_req[u][c];
                    }
                }
                eval_ans[u] = eval;
                top--;
                continue;
            }

            if (state[u] == 0) {
                // Phase 0: Pushing Left Child requirements
                int L = left_child[u];
                int R = right_child[u];
                long long W = pow2[sz[R] - 1]; // Unconstrained right tree multiplier
                
                node_req[L][0] = mul(W, add(node_req[u][0], node_req[u][2]));
                node_req[L][1] = mul(W, add(node_req[u][1], node_req[u][0]));
                node_req[L][2] = mul(W, add(node_req[u][2], node_req[u][1]));
                
                state[u] = 1;
                u_stack[++top] = L;
                state[L] = 0;
                
            } else if (state[u] == 1) {
                // Phase 1: Left evaluated, pushing restricted Right Child requirements
                int L = left_child[u];
                int R = right_child[u];
                int eval_L = eval_ans[L];
                
                node_req[R][0] = node_req[R][1] = node_req[R][2] = 0;
                if (eval_L == 0) {
                    node_req[R][1] = node_req[u][0]; 
                    node_req[R][2] = node_req[u][2]; 
                } else if (eval_L == 1) {
                    node_req[R][0] = node_req[u][0]; 
                    node_req[R][2] = node_req[u][1]; 
                } else if (eval_L == 2) {
                    node_req[R][0] = node_req[u][2]; 
                    node_req[R][1] = node_req[u][1]; 
                }
                
                state[u] = 2;
                u_stack[++top] = R;
                state[R] = 0;
                
            } else {
                // Phase 2: Resolving Subtree Winner
                int eval_L = eval_ans[left_child[u]];
                int eval_R = eval_ans[right_child[u]];
                int e = -1;
                
                if (eval_L != -1 && eval_R != -1) {
                    if ((eval_L == 0 && eval_R == 1) || (eval_L == 1 && eval_R == 0)) e = 0;
                    else if ((eval_L == 1 && eval_R == 2) || (eval_L == 2 && eval_R == 1)) e = 1;
                    else if ((eval_L == 2 && eval_R == 0) || (eval_L == 0 && eval_R == 2)) e = 2;
                }
                
                eval_ans[u] = e;
                top--;
            }
        }
        
        if (ans.length() == N) {
            cout << ans << "\n";
        } else {
            cout << "-1\n";
        }
    }
}

int main() {
    // Aggressively optimize Input/Output stream routines
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // Precompute bounded combinations multiplier
    pow2[0] = 1;
    for (int i = 1; i < MAXN * 2; i++) pow2[i] = mul(pow2[i - 1], 2);
    
    int t;
    if (cin >> t) {
        while (t--) solve();
    }
    return 0;
}