#1159216 (C++23(gnu拡張)) No.3510 RPS Eliminations

• 問題: No.3510 RPS Eliminations
• ユーザー: はじっこゆーれー
• 提出日時: 2026-04-18 06:13:53
• 言語: C++23(gnu拡張) (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,661 bytes
• コンパイル時間: 2,522 ms
• コンパイル使用メモリ: 218,056 KB
• 実行使用メモリ: 131,932 KB
• 最終ジャッジ日時: 2026-04-18 06:14:43
• 合計ジャッジ時間: 14,805 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	-- * 1
other	AC * 5 TLE * 2 -- * 21

ソースコード

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const long long INF = 2000000000000000000LL;
inline long long add(long long a, long long b) {
    long long res = a + b;
    return res >= INF ? INF : res;
}
inline long long mul(long long a, long long b) {
    if (!a || !b) return 0;
    unsigned __int128 res = (unsigned __int128)a * b;
    return res >= INF ? INF : (long long)res;
}
struct Vec {
    long long v[3];
    Vec() { v[0] = v[1] = v[2] = 0; }
    Vec(long long r, long long p, long long s) { v[0] = r; v[1] = p; v[2] = s; }
};
struct Mat {
    long long m[3][3];
    Mat() {
        m[0][0]=m[0][1]=m[0][2]=0;
        m[1][0]=m[1][1]=m[1][2]=0;
        m[2][0]=m[2][1]=m[2][2]=0;
    }
    static Mat identity() {
        Mat res;
        res.m[0][0] = res.m[1][1] = res.m[2][2] = 1;
        return res;
    }
    inline Mat operator*(const Mat& o) const {
        Mat r;
        for (int i = 0; i < 3; ++i) {
            long long m0 = m[i][0], m1 = m[i][1], m2 = m[i][2];
            if (m0) {
                r.m[i][0] = add(r.m[i][0], mul(m0, o.m[0][0]));
                r.m[i][1] = add(r.m[i][1], mul(m0, o.m[0][1]));
                r.m[i][2] = add(r.m[i][2], mul(m0, o.m[0][2]));
            }
            if (m1) {
                r.m[i][0] = add(r.m[i][0], mul(m1, o.m[1][0]));
                r.m[i][1] = add(r.m[i][1], mul(m1, o.m[1][1]));
                r.m[i][2] = add(r.m[i][2], mul(m1, o.m[1][2]));
            }
            if (m2) {
                r.m[i][0] = add(r.m[i][0], mul(m2, o.m[2][0]));
                r.m[i][1] = add(r.m[i][1], mul(m2, o.m[2][1]));
                r.m[i][2] = add(r.m[i][2], mul(m2, o.m[2][2]));
            }
        }
        return r;
    }
};
inline Mat make_matrix(const Vec& A) {
    Mat M;
    M.m[0][0] = A.v[2]; M.m[0][2] = A.v[0];
    M.m[1][1] = A.v[0]; M.m[1][0] = A.v[1];
    M.m[2][2] = A.v[1]; M.m[2][1] = A.v[2];
    return M;
}
inline Vec operator*(const Mat& m, const Vec& v) {
    Vec r;
    r.v[0] = add(mul(m.m[0][0], v.v[0]), add(mul(m.m[0][1], v.v[1]), mul(m.m[0][2], v.v[2])));
    r.v[1] = add(mul(m.m[1][0], v.v[0]), add(mul(m.m[1][1], v.v[1]), mul(m.m[1][2], v.v[2])));
    r.v[2] = add(mul(m.m[2][0], v.v[0]), add(mul(m.m[2][1], v.v[1]), mul(m.m[2][2], v.v[2])));
    return r;
}
struct BIT {
    int n, lg;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {
        lg = 0;
        while ((1 << (lg + 1)) <= n) lg++;
    }
    inline void add(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    inline int find_kth(int k) {
        int idx = 0;
        for (int i = lg; i >= 0; i--) {
            int next_idx = idx + (1 << i);
            if (next_idx <= n && tree[next_idx] < k) {
                idx = next_idx;
                k -= tree[idx];
            }
        }
        return idx + 1;
    }
};
struct SegTree {
    int n;
    vector<Mat> tree;
    void init(int _n) {
        n = _n;
        tree.assign(2 * n, Mat::identity());
    }
    void build() {
        for (int i = n - 1; i > 0; --i) {
            tree[i] = tree[i << 1] * tree[i << 1 | 1];
        }
    }
    inline void update(int p, const Mat& val) {
        for (tree[p += n] = val; p >>= 1; ) {
            tree[p] = tree[p << 1] * tree[p << 1 | 1];
        }
    }
    inline Mat query(int l, int r) {
        if (l > r) return Mat::identity();
        Mat resL = Mat::identity(), resR = Mat::identity();
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resL = resL * tree[l++];
            if (r & 1) resR = tree[--r] * resR;
        }
        return resL * resR;
    }
};
long long pow2[200005];
void solve() {
    int N;
    long long K;
    if (!(cin >> N >> K)) return;
    vector<int> A(N - 1);
    for (int i = 0; i < N - 1; i++) cin >> A[i];
    int V = 2 * N - 1;
    vector<int> L(V, -1), R(V, -1), parent(V, -1);
    BIT bit(N);
    vector<int> pos_to_node(N + 1);
    for (int i = 1; i <= N; i++) {
        bit.add(i, 1);
        pos_to_node[i] = i - 1;
    }
    for (int i = 0; i < N - 1; i++) {
        int p1 = bit.find_kth(A[i]);
        int p2 = bit.find_kth(A[i] + 1);
        int u = pos_to_node[p1];
        int v = pos_to_node[p2];
        int new_node = N + i;
        L[new_node] = u; R[new_node] = v;
        parent[u] = new_node; parent[v] = new_node;
        pos_to_node[p1] = new_node;
        bit.add(p2, -1);
    }
    int root = 2 * N - 2;
    vector<int> sz(V, 0), heavy(V, -1);
    auto dfs_sz = [&](auto& self, int u) -> void {
        if (u < N) {
            sz[u] = 1;
            return;
        }
        self(self, L[u]); self(self, R[u]);
        sz[u] = sz[L[u]] + sz[R[u]];
        if (sz[L[u]] >= sz[R[u]]) heavy[u] = L[u];
        else heavy[u] = R[u];
    };
    dfs_sz(dfs_sz, root);
    vector<int> head(V, -1), in(V, -1), tail(V, -1);
    int timer = 0;
    auto dfs_hld = [&](auto& self, int u, int h) -> void {
        head[u] = h;
        in[u] = timer++;
        if (heavy[u] != -1) {
            self(self, heavy[u], h);
            tail[u] = tail[heavy[u]];
        } else {
            tail[u] = u;
        }
        if (L[u] != -1 && L[u] != heavy[u]) self(self, L[u], L[u]);
        if (R[u] != -1 && R[u] != heavy[u]) self(self, R[u], R[u]);
    };
    dfs_hld(dfs_hld, root, root);
    SegTree initial_seg;
    initial_seg.init(V);
    vector<Vec> initial_leaf_vec(V);
    for (int i = 0; i < N; i++) {
        initial_leaf_vec[i] = Vec(pow2[sz[i] - 1], pow2[sz[i] - 1], pow2[sz[i] - 1]);
    }
    for (int u = N; u < V; u++) {
        int light = (L[u] == heavy[u]) ? R[u] : L[u];
        Vec light_val = Vec(pow2[sz[light] - 1], pow2[sz[light] - 1], pow2[sz[light] - 1]);
        initial_seg.tree[initial_seg.n + in[u]] = make_matrix(light_val);
    }
    initial_seg.build();
    SegTree seg;
    vector<Vec> leaf_vec;
    auto get_path_W = [&](int h) -> Vec {
        int bottom = tail[h];
        Mat m = seg.query(in[h], in[bottom] - 1);
        return m * leaf_vec[bottom];
    };
    auto update_leaf = [&](int leaf_idx, Vec new_W) {
        leaf_vec[leaf_idx] = new_W;
        int curr = leaf_idx;
        while (curr != -1) {
            int h = head[curr];
            Vec top_W = get_path_W(h);
            int p = parent[h];
            if (p != -1) {
                seg.update(in[p], make_matrix(top_W));
            }
            curr = p;
        }
    };
    for (int target : {0, 1, 2}) {
        seg = initial_seg;
        leaf_vec = initial_leaf_vec;
        long long K_rem = K;
        string ans = "";
        ans.reserve(N);
        bool possible = true;
        for (int i = 0; i < N; i++) {
            bool found = false;
            for (int c : {1, 0, 2}) {
                Vec v(0, 0, 0);
                v.v[c] = 1;
                update_leaf(i, v);
                long long ways = get_path_W(head[root]).v[target];
                if (K_rem <= ways) {
                    ans += (c == 0 ? 'R' : (c == 1 ? 'P' : 'S'));
                    found = true;
                    break;
                } else {
                    K_rem -= ways;
                }
            }
            if (!found) {
                possible = false;
                break;
            }
        }
        if (possible) cout << ans << "\n";
        else cout << "-1\n";
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pow2[0] = 1;
    for (int i = 1; i <= 200000; i++) pow2[i] = min(INF, pow2[i - 1] * 2LL);
    int T;
    if (cin >> T) {
        while (T--) solve();
    }
    return 0;
}