結果
| 問題 | No.3509 Get More Money |
| コンテスト | |
| ユーザー |
 gojoxd
|
| 提出日時 | 2026-04-18 20:17:53 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,554 bytes |
| 記録 | |
| コンパイル時間 | 1,520 ms |
| コンパイル使用メモリ | 179,608 KB |
| 実行使用メモリ | 28,288 KB |
| 最終ジャッジ日時 | 2026-04-18 20:18:55 |
| 合計ジャッジ時間 | 11,436 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 59 |
ソースコード
#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);
}
// 0: P, 1: R, 2: S
int win_char(int a, int b) {
if ((a == 0 && b == 1) || (a == 1 && b == 0)) return 0; // P beats R
if ((a == 1 && b == 2) || (a == 2 && b == 1)) return 1; // R beats S
if ((a == 2 && b == 0) || (a == 0 && b == 2)) return 2; // S beats P
return -1; // Ties do not naturally occur in valid evaluations
}
const int MAXN = 200005;
int left_child[MAXN * 2], right_child[MAXN * 2], parent_node[MAXN * 2];
int sz[MAXN * 2];
bool has_right_ancestor[MAXN * 2];
long long pow2[MAXN];
int eval_c[MAXN * 2];
int jump[MAXN * 2];
int map_c[MAXN * 2][3];
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(int u, bool has_right) {
sz[u] = 1;
has_right_ancestor[u] = has_right;
if (left_child[u] == 0) return;
dfs(left_child[u], has_right);
dfs(right_child[u], true);
sz[u] = sz[left_child[u]] + sz[right_child[u]];
}
void solve() {
int N; long long K;
cin >> N >> K;
vector<int> A(N);
for (int i = 1; i < N; i++) cin >> A[i];
if (K > pow2[N - 1]) {
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;
left_child[i] = right_child[i] = parent_node[i] = 0;
}
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;
dfs(root, false);
int target_order[3] = {1, 0, 2}; // Output order must be: R, P, S
for (int i = 0; i < 3; i++) {
int target = target_order[i];
for (int j = 1; j <= 2 * N - 1; j++) eval_c[j] = -1;
long long current_k = K;
string ans = "";
for (int leaf = 1; leaf <= N; leaf++) {
int chosen_c = -1;
for (int c = 0; c < 3; ++c) {
long long dp[3] = {0, 0, 0};
dp[c] = 1;
int curr = leaf;
while (curr != root) {
int p = parent_node[curr];
if (curr == left_child[p]) {
int R = right_child[p];
long long W = pow2[sz[R] - 1];
long long nxt[3];
// FIX: Corrected combinatorial logic
// P needs (P, R), R needs (R, S), S needs (S, P)
nxt[0] = min(INF, W * (dp[0] + dp[1])); // P beats R
nxt[1] = min(INF, W * (dp[1] + dp[2])); // R beats S
nxt[2] = min(INF, W * (dp[2] + dp[0])); // S beats P
dp[0] = nxt[0]; dp[1] = nxt[1]; dp[2] = nxt[2];
curr = p;
// Extremely aggressive early break
if (dp[0] == INF && dp[1] == INF && dp[2] == INF && !has_right_ancestor[curr]) break;
} else {
// O(1) Fast-forward over evaluated right subtrees
int top = jump[curr];
long long nxt[3] = {0, 0, 0};
for (int x = 0; x < 3; ++x) {
if (dp[x] > 0) {
int res = map_c[curr][x];
if (res != -1) nxt[res] = add(nxt[res], dp[x]);
}
}
dp[0] = nxt[0]; dp[1] = nxt[1]; dp[2] = nxt[2];
curr = top;
}
}
long long ways = dp[target];
if (ways >= current_k) {
chosen_c = c;
break;
} else {
current_k -= ways;
}
}
ans += (chosen_c == 0 ? 'P' : (chosen_c == 1 ? 'R' : 'S'));
// Systematically lock evaluated paths & Build jump pointers dynamically
eval_c[leaf] = chosen_c;
int curr = leaf;
while (curr != root) {
int p = parent_node[curr];
if (curr == right_child[p]) {
int L = left_child[p];
eval_c[p] = win_char(eval_c[L], eval_c[curr]);
curr = p;
} else {
break;
}
}
// FIX: Caught Undefined Behavior (-1 index read)
if (curr != root) {
int p = parent_node[curr];
int R = right_child[p];
if (parent_node[p] != 0 && p == right_child[parent_node[p]]) {
jump[R] = jump[p];
for (int x = 0; x < 3; ++x) {
int w = win_char(eval_c[curr], x);
map_c[R][x] = (w == -1 ? -1 : map_c[p][w]);
}
} else {
jump[R] = p;
for (int x = 0; x < 3; ++x) {
map_c[R][x] = win_char(eval_c[curr], x);
}
}
}
}
cout << ans << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
pow2[0] = 1;
for (int i = 1; i < MAXN; i++) pow2[i] = min(INF, pow2[i - 1] * 2);
int t;
if (cin >> t) while (t--) solve();
return 0;
}