結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 はじっこゆーれー
|
| 提出日時 | 2026-04-18 06:10:14 |
| 言語 | C++23(gnu拡張) (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,856 bytes |
| 記録 | |
| コンパイル時間 | 1,974 ms |
| コンパイル使用メモリ | 204,452 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-04-18 06:11:11 |
| 合計ジャッジ時間 | 20,842 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | AC * 2 TLE * 4 -- * 22 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const long long INF = 2e18;
long long add(long long a, long long b) {
return min(INF, a + b);
}
long long mul(long long a, long long b) {
if (a == 0 || b == 0) return 0;
if (INF / a < b) return INF;
return a * b;
}
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() { memset(m, 0, sizeof(m)); }
Mat operator*(const Mat& o) const {
Mat r;
for (int i = 0; i < 3; ++i) {
for (int k = 0; k < 3; ++k) {
if (m[i][k]) {
for (int j = 0; j < 3; ++j) {
r.m[i][j] = add(r.m[i][j], mul(m[i][k], o.m[k][j]));
}
}
}
}
return r;
}
};
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;
}
Vec operator*(const Mat& m, const Vec& v) {
Vec r;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
r.v[i] = add(r.v[i], mul(m.m[i][j], v.v[j]));
}
}
return r;
}
struct BIT {
int n;
vector<int> tree;
BIT(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 = 20; 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;
SegTree() {}
SegTree(int n) : n(n), tree(4 * n) {
for (int i = 0; i < 4 * n; i++) {
for (int j = 0; j < 3; j++) tree[i].m[j][j] = 1;
}
}
void update(int node, int start, int end, int idx, const Mat& val) {
if (start == end) {
tree[node] = val;
return;
}
int mid = (start + end) / 2;
if (idx <= mid) update(2 * node, start, mid, idx, val);
else update(2 * node + 1, mid + 1, end, idx, val);
tree[node] = tree[2 * node] * tree[2 * node + 1];
}
Mat query(int node, int start, int end, int l, int r) {
if (r < start || end < l) {
Mat id;
for (int i = 0; i < 3; i++) id.m[i][i] = 1;
return id;
}
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(2 * node, start, mid, l, r) * query(2 * node + 1, mid + 1, end, l, r);
}
};
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(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.update(1, 0, V - 1, in[u], make_matrix(light_val));
}
SegTree seg;
vector<Vec> leaf_vec;
auto get_path_W = [&](int h) -> Vec {
int bottom = tail[h];
Mat m = seg.query(1, 0, V - 1, 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(1, 0, V - 1, 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 = "";
bool possible = true;
for (int i = 0; i < N; i++) {
bool found = false;
// 辞書順のため P, R, S の順に試す (P=1, R=0, S=2)
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] * 2);
int T;
if (cin >> T) {
while (T--) solve();
}
return 0;
}