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

• 問題: No.3510 RPS Eliminations
• ユーザー: ,
• 提出日時: 2026-04-19 18:51:01
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 3,120 bytes
• コンパイル時間: 3,492 ms
• コンパイル使用メモリ: 343,680 KB
• 実行使用メモリ: 21,696 KB
• 最終ジャッジ日時: 2026-04-19 18:51:39
• 合計ジャッジ時間: 7,051 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int WIN_TBL[3][3] = {
    {-1, 0, 2},
    { 0,-1, 1},
    { 2, 1,-1}
};

const int MAXN = 200002;

int par[2*MAXN], lc[2*MAXN], rc[2*MAXN];
ll dp[2*MAXN][3];

void combine(int v) {
    ll *dl = dp[lc[v]], *dr = dp[rc[v]];
    ll *res = dp[v];

    res[0] = res[1] = res[2] = 0;

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (WIN_TBL[i][j] != -1) {
                res[WIN_TBL[i][j]] += dl[i] * dr[j];
            }
        }
    }
}

void update_up(int v) {
    while (par[v] != -1) {
        v = par[v];
        combine(v);
    }
}

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

    vector<int> A(N-1);
    for (auto &x : A) cin >> x;

    // ===== FIXED STRUCTURE =====
    list<int> alive;
    vector<list<int>::iterator> it(N);

    for (int i = 0; i < N; i++) {
        alive.push_back(i);
    }

    auto get_kth = [&](int k) {
        auto cur = alive.begin();
        advance(cur, k-1);
        return cur;
    };

    fill(par, par + 2*N, -1);

    int next_node = N;

    // initial mapping
    vector<int> node(N);
    iota(node.begin(), node.end(), 0);

    for (int i = 0; i < N-1; i++) {
        auto ita = get_kth(A[i]);
        auto itb = next(ita);

        int a = *ita;
        int b = *itb;

        int v = next_node++;

        lc[v] = node[a];
        rc[v] = node[b];

        par[lc[v]] = par[rc[v]] = v;

        alive.erase(itb);
        *ita = v;
        node[v] = v;
    }

    int root = *alive.begin();

    // ===== INIT DP =====
    for (int i = 0; i < 2*N; i++)
        dp[i][0] = dp[i][1] = dp[i][2] = 1;

    for (int i = N; i < next_node; i++)
        combine(i);

    string res_names[3];
    string chars = "PRS";

    vector<array<ll,3>> dp_init(next_node);
    for (int i = 0; i < next_node; i++)
        dp_init[i] = {dp[i][0], dp[i][1], dp[i][2]};

    for (int target = 0; target < 3; target++) {

        if (dp_init[root][target] < K) {
            res_names[target] = "-1";
            continue;
        }

        for (int i = 0; i < next_node; i++)
            for (int j = 0; j < 3; j++)
                dp[i][j] = dp_init[i][j];

        ll rem = K;
        string ans(N, '?');

        for (int i = 0; i < N; i++) {
            for (int c = 0; c < 3; c++) {

                ll saved[3] = {dp[i][0], dp[i][1], dp[i][2]};

                dp[i][0] = dp[i][1] = dp[i][2] = 0;
                dp[i][c] = 1;

                update_up(i);

                ll cnt = dp[root][target];

                if (cnt >= rem) {
                    ans[i] = chars[c];
                    break;
                } else {
                    rem -= cnt;
                    for (int t = 0; t < 3; t++) dp[i][t] = saved[t];
                    update_up(i);
                }
            }
        }

        res_names[target] = ans;
    }

    cout << res_names[1] << "\n"
         << res_names[0] << "\n"
         << res_names[2] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
}