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

• 問題: No.3509 Get More Money
• ユーザー: gojoxd
• 提出日時: 2026-04-18 20:32:24
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,759 bytes
• コンパイル時間: 1,941 ms
• コンパイル使用メモリ: 178,868 KB
• 実行使用メモリ: 29,056 KB
• 最終ジャッジ日時: 2026-04-18 20:33:18
• 合計ジャッジ時間: 12,528 ms
• ジャッジサーバーID （参考情報）: judge2_0 / 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 tracking 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 K_global;
string ans;

// 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;
    }
};

// Calculate size (number of leaves) in each subtree
void dfs_sz(int u) {
    if (u == 0) return;
    if (left_child[u] == 0) {
        sz[u] = 1;
        return;
    }
    dfs_sz(left_child[u]);
    dfs_sz(right_child[u]);
    sz[u] = sz[left_child[u]] + sz[right_child[u]];
}

// O(N) Top-Down exact path resolution!
int solve_tree(int u, long long req[3]) {
    // If it's a leaf, lock in the character based on the K constraint
    if (left_child[u] == 0) {
        for (int c = 0; c < 3; ++c) {
            if (req[c] >= K_global) {
                ans += (c == 0 ? 'P' : (c == 1 ? 'R' : 'S'));
                return c;
            } else {
                K_global -= req[c];
            }
        }
        return -1;
    }

    int L = left_child[u];
    int R = right_child[u];
    long long W = pow2[sz[R] - 1]; // Unconstrained right tree multiplier

    // Pass requirements down to the Left Child
    long long req_L[3];
    req_L[0] = mul(W, add(req[0], req[2])); // To get P, we need (P beats R) or (S beats P)
    req_L[1] = mul(W, add(req[1], req[0])); // To get R, we need (R beats S) or (P beats R)
    req_L[2] = mul(W, add(req[2], req[1])); // To get S, we need (S beats P) or (R beats S)

    int eval_L = solve_tree(L, req_L);

    // Now that Left is locked, pass strict remaining requirements to Right Child
    long long req_R[3] = {0, 0, 0};
    if (eval_L == 0) { // Left is P
        req_R[1] = req[0]; // If R is R, P wins
        req_R[2] = req[2]; // If R is S, S wins
    } else if (eval_L == 1) { // Left is R
        req_R[0] = req[0]; 
        req_R[2] = req[1]; 
    } else if (eval_L == 2) { // Left is S
        req_R[0] = req[2]; 
        req_R[1] = req[1]; 
    }

    int eval_R = solve_tree(R, req_R);

    // Return the evaluated winner for upstream tracking
    if ((eval_L == 0 && eval_R == 1) || (eval_L == 1 && eval_R == 0)) return 0;
    if ((eval_L == 1 && eval_R == 2) || (eval_L == 2 && eval_R == 1)) return 1;
    if ((eval_L == 2 && eval_R == 0) || (eval_L == 0 && eval_R == 2)) return 2;
    return -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
    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;
    }

    // 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);
    }
    
    int root = 2 * N - 1;
    dfs_sz(root);

    // Requested alphabetical 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];
        K_global = K;
        ans = "";
        
        long long req[3] = {0, 0, 0};
        req[target] = 1; // Assert root requirement
        
        solve_tree(root, req);
        
        if (ans.length() == N) {
            cout << ans << "\n";
        } else {
            cout << "-1\n";
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.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;
}