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

• 問題: No.3509 Get More Money
• ユーザー: gojoxd
• 提出日時: 2026-04-18 19:56:03
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,445 bytes
• コンパイル時間: 2,031 ms
• コンパイル使用メモリ: 178,424 KB
• 実行使用メモリ: 173,952 KB
• 最終ジャッジ日時: 2026-04-18 19:56:51
• 合計ジャッジ時間: 10,979 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_0

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

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <array>

using namespace std;

const long long INF = 1000000000000000001LL; // 10^18 + 1 to prevent overflow

// Saturated addition
long long add(long long a, long long b) {
    return min(INF, a + b);
}

// Saturated multiplication
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
// P beats R, R beats S, S beats P
int lose(int c) {
    return (c + 1) % 3;
}

int N;
long long K;
vector<int> A;
vector<int> left_child, right_child, parent;
vector<array<long long, 3>> dp;

// Fenwick tree to track active elements and simulate the exact tree merges
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) { // 2^18 > 200000
            if (idx + i <= n && tree[idx + i] < k) {
                idx += i;
                k -= tree[idx];
            }
        }
        return idx + 1;
    }
};

// Re-evaluates a single node based on its children
void update_node(int u) {
    int L = left_child[u];
    int R = right_child[u];
    for (int c = 0; c < 3; ++c) {
        int lc = lose(c);
        dp[u][c] = add(mul(dp[L][c], dp[R][lc]), mul(dp[L][lc], dp[R][c]));
    }
}

// Propagates state upwards until a node's state no longer changes
void propagate(int u) {
    while (parent[u] != 0) {
        u = parent[u];
        array<long long, 3> old_dp = dp[u];
        update_node(u);
        
        // Critical optimization: break early if combinations saturate/stabilize
        if (dp[u] == old_dp) break;
    }
}

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

    left_child.assign(2 * N, 0);
    right_child.assign(2 * N, 0);
    parent.assign(2 * N, 0);
    dp.assign(2 * N, {0, 0, 0});

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

    // Phase 1: Build the evaluation tree structure
    for (int i = 1; i < N; i++) {
        int pos1 = fenw.find_kth(A[i]);
        int pos2 = fenw.find_kth(A[i] + 1);
        int u = node_at[pos1];
        int v = node_at[pos2];
        
        int idx = N + i;
        left_child[idx] = u;
        right_child[idx] = v;
        parent[u] = idx;
        parent[v] = idx;
        
        node_at[pos1] = idx;
        fenw.add(pos2, -1);
    }

    int root = 2 * N - 1;
    
    // Process targets in the exact output order requested: R, P, S
    // Mapped as: R = 1, P = 0, S = 2
    int target_order[3] = {1, 0, 2};

    for (int target : target_order) {
        // Reset the evaluation tree assuming all leaves are completely unrestricted
        for (int i = 1; i <= N; i++) dp[i] = {1, 1, 1};
        for (int i = N + 1; i <= 2 * N - 1; i++) update_node(i);

        // Quick check if the target string is even possible
        if (dp[root][target] < K) {
            cout << "-1\n";
            continue;
        }

        long long current_k = K;
        string ans = "";
        
        // Phase 2: Traverse leaf by leaf to determine the K-th lexicographical string
        for (int i = 1; i <= N; i++) {
            // Lexicographical alphabetical testing: 'P', then 'R', then 'S'
            for (int c = 0; c < 3; ++c) {
                // Apply a tentative character constraint and bubble up
                dp[i] = {0, 0, 0};
                dp[i][c] = 1;
                propagate(i);

                if (dp[root][target] >= current_k) {
                    // This character branch contains our K-th target string, so we lock it
                    if (c == 0) ans += 'P';
                    else if (c == 1) ans += 'R';
                    else ans += 'S';
                    break;
                } else {
                    // Not in this branch, decrease the K target and test the next character
                    current_k -= dp[root][target];
                }
            }
        }
        cout << ans << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}