結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー gojoxd
提出日時 2026-04-18 20:03:52
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 7,177 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,708 ms
コンパイル使用メモリ 207,192 KB
実行使用メモリ 242,876 KB
最終ジャッジ日時 2026-04-18 20:04:45
合計ジャッジ時間 15,893 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 5 TLE * 2 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize("O3,unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

const long long INF = 1000000000000000001LL;

inline long long add(long long a, long long b) { return min(INF, a + b); }
inline 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);
}

// 3x3 Matrix for Dynamic DP
struct Mat {
    long long m[3][3];
    Mat() {
        for(int i=0; i<3; ++i) for(int j=0; j<3; ++j) m[i][j] = 0;
    }
    Mat operator*(const Mat& other) const {
        Mat res;
        for(int i=0; i<3; ++i) {
            for(int k=0; k<3; ++k) {
                if (m[i][k] == 0) continue;
                for(int j=0; j<3; ++j) {
                    res.m[i][j] = add(res.m[i][j], mul(m[i][k], other.m[k][j]));
                }
            }
        }
        return res;
    }
};

// Coefficient matrix for an internal node
Mat get_matrix(long long v[3]) {
    Mat res;
    res.m[0][0] = v[1]; res.m[0][1] = v[0]; res.m[0][2] = 0;
    res.m[1][0] = 0;    res.m[1][1] = v[2]; res.m[1][2] = v[1];
    res.m[2][0] = v[2]; res.m[2][1] = 0;    res.m[2][2] = v[0];
    return res;
}

// Matrix representation of a leaf vector
Mat get_leaf_matrix(long long v[3]) {
    Mat res;
    res.m[0][0] = v[0];
    res.m[1][0] = v[1];
    res.m[2][0] = v[2];
    return res;
}

const int MAXN = 200005;
int N;
long long K;
int left_child[MAXN * 2], right_child[MAXN * 2], parent_node[MAXN * 2];
int sz[MAXN * 2], heavy[MAXN * 2], light[MAXN * 2];
int top_node[MAXN * 2], in[MAXN * 2], pos_to_node[MAXN * 2];
int end_of_heavy[MAXN * 2];
int timer_hld;
long long V[MAXN * 2][3];

Mat tree_seg[MAXN * 8];

// Fenwick tree to track active elements during 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) {
            if (idx + i <= n && tree[idx + i] < k) {
                idx += i;
                k -= tree[idx];
            }
        }
        return idx + 1;
    }
};

void dfs_sz(int u) {
    sz[u] = 1; heavy[u] = light[u] = 0;
    if (u <= N) return;
    dfs_sz(left_child[u]);
    dfs_sz(right_child[u]);
    sz[u] += sz[left_child[u]] + sz[right_child[u]];
    if (sz[left_child[u]] > sz[right_child[u]]) {
        heavy[u] = left_child[u]; light[u] = right_child[u];
    } else {
        heavy[u] = right_child[u]; light[u] = left_child[u];
    }
}

void dfs_hld(int u, int t) {
    top_node[u] = t;
    in[u] = ++timer_hld;
    pos_to_node[timer_hld] = u;
    if (u <= N) {
        end_of_heavy[t] = u;
        return;
    }
    dfs_hld(heavy[u], t);
    dfs_hld(light[u], light[u]);
}

void dfs_init_V(int u) {
    if (u <= N) {
        V[u][0] = V[u][1] = V[u][2] = 1;
        return;
    }
    int L = left_child[u], R = right_child[u];
    dfs_init_V(L); dfs_init_V(R);
    V[u][0] = add(mul(V[L][0], V[R][1]), mul(V[L][1], V[R][0]));
    V[u][1] = add(mul(V[L][1], V[R][2]), mul(V[L][2], V[R][1]));
    V[u][2] = add(mul(V[L][2], V[R][0]), mul(V[L][0], V[R][2]));
}

void build_seg(int node, int L, int R) {
    if (L == R) {
        int u = pos_to_node[L];
        if (u <= N) tree_seg[node] = get_leaf_matrix(V[u]);
        else tree_seg[node] = get_matrix(V[light[u]]);
        return;
    }
    int mid = (L + R) / 2;
    build_seg(node * 2, L, mid);
    build_seg(node * 2 + 1, mid + 1, R);
    tree_seg[node] = tree_seg[node * 2] * tree_seg[node * 2 + 1];
}

void update_seg(int node, int L, int R, int pos, const Mat& val) {
    if (L == R) { tree_seg[node] = val; return; }
    int mid = (L + R) / 2;
    if (pos <= mid) update_seg(node * 2, L, mid, pos, val);
    else update_seg(node * 2 + 1, mid + 1, R, pos, val);
    tree_seg[node] = tree_seg[node * 2] * tree_seg[node * 2 + 1];
}

Mat query_seg(int node, int L, int R, int qL, int qR) {
    if (qL <= L && R <= qR) return tree_seg[node];
    int mid = (L + R) / 2;
    if (qR <= mid) return query_seg(node * 2, L, mid, qL, qR);
    if (qL > mid) return query_seg(node * 2 + 1, mid + 1, R, qL, qR);
    return query_seg(node * 2, L, mid, qL, qR) * query_seg(node * 2 + 1, mid + 1, R, qL, qR);
}

void update_leaf(int leaf, long long new_V[3]) {
    V[leaf][0] = new_V[0]; V[leaf][1] = new_V[1]; V[leaf][2] = new_V[2];
    update_seg(1, 1, timer_hld, in[leaf], get_leaf_matrix(V[leaf]));
    
    int u = leaf;
    while (u != 0) {
        int t = top_node[u];
        Mat res = query_seg(1, 1, timer_hld, in[t], in[end_of_heavy[t]]);
        V[t][0] = res.m[0][0]; V[t][1] = res.m[1][0]; V[t][2] = res.m[2][0];
        
        int p = parent_node[t];
        if (p != 0) update_seg(1, 1, timer_hld, in[p], get_matrix(V[t]));
        u = p;
    }
}

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

    long long max_k = 1; bool k_valid = false;
    for (int i = 1; i < N; i++) {
        max_k *= 2;
        if (max_k >= K) { k_valid = true; break; }
    }
    if (!k_valid) { cout << "-1\n-1\n-1\n"; return; }

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

    for (int i = 1; i < N; i++) {
        int p1 = fenw.find_kth(A[i]), p2 = fenw.find_kth(A[i] + 1);
        int u = node_at[p1], v = node_at[p2];
        int idx = N + i;
        left_child[idx] = u; right_child[idx] = v;
        parent_node[u] = parent_node[v] = idx;
        node_at[p1] = idx; fenw.add(p2, -1);
    }
    int root = 2 * N - 1;
    parent_node[root] = 0; timer_hld = 0;

    dfs_sz(root);
    dfs_hld(root, root);
    dfs_init_V(root);
    build_seg(1, 1, timer_hld);

    // Fast copy system state
    vector<Mat> backup_tree(tree_seg + 1, tree_seg + 1 + 4 * timer_hld);
    long long backup_V[MAXN * 2][3];
    for (int i = 1; i <= 2 * N - 1; i++) for (int j = 0; j < 3; j++) backup_V[i][j] = V[i][j];

    int target_order[3] = {1, 0, 2}; // R, P, S

    for (int i = 0; i < 3; i++) {
        if (i > 0) {
            for (int j = 1; j <= 4 * timer_hld; j++) tree_seg[j] = backup_tree[j - 1];
            for (int j = 1; j <= 2 * N - 1; j++) for (int k = 0; k < 3; k++) V[j][k] = backup_V[j][k];
        }

        int target = target_order[i];
        if (V[root][target] < K) {
            cout << "-1\n"; continue;
        }

        long long current_k = K;
        string ans = "";
        for (int j = 1; j <= N; j++) {
            for (int c = 0; c < 3; ++c) {
                long long newV[3] = {0, 0, 0}; newV[c] = 1;
                update_leaf(j, newV);
                
                if (V[root][target] >= current_k) {
                    ans += (c == 0 ? 'P' : (c == 1 ? 'R' : 'S'));
                    break;
                } else {
                    current_k -= V[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;
}
0