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

• 問題: No.3510 RPS Eliminations
• ユーザー: 왕지후
• 提出日時: 2026-04-18 11:39:20
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,063 bytes
• コンパイル時間: 2,656 ms
• コンパイル使用メモリ: 166,616 KB
• 実行使用メモリ: 48,500 KB
• 最終ジャッジ日時: 2026-04-18 11:39:37
• 合計ジャッジ時間: 16,625 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

ファイルパターン	結果
sample	AC * 1
other	AC * 10 WA * 18

ソースコード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const long long INF_CAP = 2000000000000000000LL; // 2 * 10^18

long long add_cap(long long a, long long b) {
    if (a + b >= INF_CAP) return INF_CAP;
    return a + b;
}

long long mul2_cap(long long W, int p) {
    if (W == 0) return 0;
    if (p >= 61) return INF_CAP;
    unsigned long long res = (unsigned long long)W << p;
    if (res >= INF_CAP) return INF_CAP;
    return res;
}

// 0: P, 1: R, 2: S (アルファベット順)
int get_winner(int x, int y) {
    if (x == y) return x;
    if (y == (x + 1) % 3) return x;
    return y;
}

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

int solve_tree(int u, int N, const vector<int>& left_child, const vector<int>& right_child, const vector<int>& sz, long long W[3], long long &k, string &ans) {
    // 葉に到達した場合
    if (u <= N) {
        for (int i = 0; i < 3; i++) {
            if (W[i] > 0) {
                if (k < W[i]) {
                    ans += (i == 0 ? 'P' : (i == 1 ? 'R' : 'S'));
                    return i;
                }
                k -= W[i];
            }
        }
        return -1;
    }

    int L = left_child[u];
    int R = right_child[u];

    // 左の子へ渡す重みの計算
    long long WL[3] = {0, 0, 0};
    for(int zl = 0; zl < 3; zl++) {
        for(int zr = 0; zr < 3; zr++) {
            if (zl == zr) continue; // 同じ手はスキップ
            int zu = get_winner(zl, zr);
            WL[zl] = add_cap(WL[zl], mul2_cap(W[zu], sz[R]));
        }
    }

    int zl = solve_tree(L, N, left_child, right_child, sz, WL, k, ans);

    // 左の子の結果から、右の子へ渡す重みの計算
    long long WR[3] = {0, 0, 0};
    for(int zr = 0; zr < 3; zr++) {
        if (zl == zr) continue;
        int zu = get_winner(zl, zr);
        WR[zr] = W[zu];
    }

    int zr = solve_tree(R, N, left_child, right_child, sz, WR, k, ans);

    return get_winner(zl, zr);
}

void solve() {
    int N;
    long long K;
    cin >> N >> K;

    vector<int> A(N);
    for (int i = 1; i < N; i++) {
        cin >> A[i];
    }

    // 文字列の組み合わせ総数が K 未満であれば -1
    if (N - 1 < 60 && K > (1LL << (N - 1))) {
        cout << "-1\n-1\n-1\n";
        return;
    }

    BIT bit(N);
    vector<int> left_child(2 * N);
    vector<int> right_child(2 * N);
    vector<int> sz(2 * N, 0);
    vector<int> active_node(N + 1);

    for (int i = 1; i <= N; i++) {
        active_node[i] = i;
    }

    // トーナメント木の構築
    for (int i = 1; i < N; i++) {
        int u_pos = bit.find_kth(A[i]);
        int v_pos = bit.find_kth(A[i] + 1);
        int id_u = active_node[u_pos];
        int id_v = active_node[v_pos];
        int new_id = N + i;
        
        left_child[new_id] = id_u;
        right_child[new_id] = id_v;
        sz[new_id] = sz[id_u] + sz[id_v] + 1;
        
        bit.add(v_pos, -1);
        active_node[u_pos] = new_id;
    }

    int root = 2 * N - 1;
    int targets[3] = {1, 0, 2}; // 出力順: R(1), P(0), S(2)

    for (int i = 0; i < 3; i++) {
        int target = targets[i];
        long long k = K - 1; // 内部では0-indexedを使用
        long long W[3] = {0, 0, 0};
        W[target] = 1;
        string ans = "";
        solve_tree(root, N, left_child, right_child, sz, W, k, ans);
        cout << ans << "\n";
    }
}

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