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

• 問題: No.3510 RPS Eliminations
• ユーザー: rumblycascade7
• 提出日時: 2026-04-18 06:07:01
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 157 ms / 2,000 ms
• コード長: 5,169 bytes
• コンパイル時間: 3,820 ms
• コンパイル使用メモリ: 346,576 KB
• 実行使用メモリ: 30,856 KB
• 最終ジャッジ日時: 2026-04-18 06:07:16
• 合計ジャッジ時間: 10,217 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_1

ファイルパターン	結果
sample	AC * 1
other	AC * 28

ソースコード

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

const ll BIG = (ll)2e18;

ll mc(ll a, ll b) {
    if (a == 0 || b == 0) return 0;
    if (a > BIG / b) return BIG;
    return a * b;
}
ll ac(ll a, ll b) {
    if (a > BIG - b) return BIG;
    return a + b;
}

const int bt[3] = {1, 2, 0};
const int wb[3] = {2, 0, 1};

int fw[200005];
int fn;

void fu(int i, int v) {
    for (; i <= fn; i += i & -i) fw[i] += v;
}
int fk(int k, int L) {
    int p = 0;
    for (int s = L; s >= 0; s--) {
        int j = p + (1 << s);
        if (j <= fn && fw[j] < k) { p = j; k -= fw[j]; }
    }
    return p + 1;
}

int lc[400005], rc[400005];
int at[200005];
ll cn[400005][3];

struct F { int v, p; ll W[3]; ll K; int c; };

int as_[200005];

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n; ll K;
        scanf("%d %lld", &n, &K);
        int nd = 2 * n - 1;
        for (int i = 1; i <= nd; i++) { lc[i] = 0; rc[i] = 0; }

        vector<int> A(n);
        for (int i = 1; i < n; i++) scanf("%d", &A[i]);

        fn = n;
        for (int i = 0; i <= n + 1; i++) fw[i] = 0;
        for (int i = 1; i <= n; i++) fu(i, 1);
        int L = 0;
        while ((1 << (L + 1)) <= n) L++;

        for (int i = 1; i <= n; i++) at[i] = i;

        for (int i = 1; i < n; i++) {
            int a = fk(A[i], L);
            int b = fk(A[i] + 1, L);
            int x = n + i;
            lc[x] = at[a];
            rc[x] = at[b];
            at[a] = x;
            fu(b, -1);
        }
        int rt = 2 * n - 1;

        vector<int> ord;
        ord.reserve(nd);
        {
            vector<pair<int,int>> st;
            st.reserve(nd);
            st.push_back({rt, 0});
            while (!st.empty()) {
                auto &t = st.back();
                if (t.second == 0) {
                    t.second = 1;
                    int v = t.first;
                    if (lc[v]) {
                        st.push_back({rc[v], 0});
                        st.push_back({lc[v], 0});
                    }
                } else {
                    ord.push_back(t.first);
                    st.pop_back();
                }
            }
        }

        for (int v : ord) {
            if (!lc[v]) {
                cn[v][0] = cn[v][1] = cn[v][2] = 1;
            } else {
                int l = lc[v], r = rc[v];
                for (int c = 0; c < 3; c++) {
                    ll a = mc(cn[l][c], cn[r][bt[c]]);
                    ll b = mc(cn[l][bt[c]], cn[r][c]);
                    cn[v][c] = ac(a, b);
                }
            }
        }

        string ans[3];
        for (int g = 0; g < 3; g++) {
            if (cn[rt][g] < K) { ans[g] = "-1"; continue; }
            for (int i = 1; i <= n; i++) as_[i] = 0;

            vector<F> st;
            st.reserve(nd + 8);
            F z;
            z.v = rt; z.p = 0;
            z.W[0] = z.W[1] = z.W[2] = 0;
            z.W[g] = 1;
            z.K = K; z.c = -1;
            st.push_back(z);

            int rcv = -1;
            ll rk = 0;

            while (!st.empty()) {
                F &f = st.back();
                int v = f.v;
                if (!lc[v]) {
                    ll k = f.K;
                    int pk = -1;
                    for (int c = 0; c < 3; c++) {
                        if (f.W[c] >= k) { pk = c; break; }
                        k -= f.W[c];
                    }
                    as_[v] = pk;
                    rcv = pk; rk = k;
                    st.pop_back();
                } else if (f.p == 0) {
                    int l = lc[v], r = rc[v];
                    ll W[3];
                    for (int c = 0; c < 3; c++) {
                        ll a = mc(f.W[c], cn[r][bt[c]]);
                        ll b = mc(f.W[wb[c]], cn[r][wb[c]]);
                        W[c] = ac(a, b);
                    }
                    f.p = 1;
                    F ch;
                    ch.v = l; ch.p = 0;
                    ch.W[0] = W[0]; ch.W[1] = W[1]; ch.W[2] = W[2];
                    ch.K = f.K; ch.c = -1;
                    st.push_back(ch);
                } else if (f.p == 1) {
                    f.c = rcv;
                    int r = rc[v];
                    int cl = f.c;
                    ll W[3] = {0, 0, 0};
                    W[bt[cl]] = f.W[cl];
                    W[wb[cl]] = f.W[wb[cl]];
                    f.p = 2;
                    F ch;
                    ch.v = r; ch.p = 0;
                    ch.W[0] = W[0]; ch.W[1] = W[1]; ch.W[2] = W[2];
                    ch.K = rk; ch.c = -1;
                    st.push_back(ch);
                } else {
                    int cr = rcv;
                    int cl = f.c;
                    int cv;
                    if (cr == bt[cl]) cv = cl;
                    else cv = wb[cl];
                    rcv = cv;
                    st.pop_back();
                }
            }

            string s;
            s.resize(n);
            for (int i = 1; i <= n; i++) s[i - 1] = "PRS"[as_[i]];
            ans[g] = s;
        }

        printf("%s\n%s\n%s\n", ans[1].c_str(), ans[0].c_str(), ans[2].c_str());
    }
    return 0;
}