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

• 問題: No.3510 RPS Eliminations
• ユーザー: Nzt3
• 提出日時: 2026-03-29 04:31:10
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 120 ms / 2,000 ms
• コード長: 3,211 bytes
• コンパイル時間: 3,395 ms
• コンパイル使用メモリ: 343,476 KB
• 実行使用メモリ: 47,820 KB
• 最終ジャッジ日時: 2026-04-17 19:50:00
• 合計ジャッジ時間: 13,156 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

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

ソースコード

#include <atcoder/segtree.hpp>
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define ov4(a, b, c, d, name, ...) name
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define fore(e, v) for (auto &&e : v)
#define all(a) begin(a), end(a)

template <typename T, typename S> bool chmin(T &a, const S &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S> bool chmax(T &a, const S &b) {
  return a < b ? a = b, 1 : 0;
}
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
  _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

void solve();

int main() {
  int T;
  cin >> T;
  rep(T) solve();
}

int seg_op(int a, int b) { return a + b; }
int seg_e() { return 0; }

void solve() {
  ll N, K;
  cin >> N >> K;
  vi A(N - 1);
  fore(i, A) cin >> i;

  auto safePow2 = [&](ll n) -> ll {
    if (n > 60)
      return INFL;
    else
      return 1ll << n;
  };
  if (safePow2(N - 1) < K) {
    cout << "-1\n-1\n-1\n";
    return;
  }

  atcoder::segtree<int, seg_op, seg_e> seg(vi(N, 1));
  vi idx(N), par(N * 2 - 1, -1), subtree(N * 2 - 1);
  par.reserve(N * 2);
  fill(begin(subtree), begin(subtree) + N, 1);
  vector<pii> child(N * 2 - 1, pii{-1, -1});
  iota(all(idx), 0);
  rep(i, N - 1) {
    int l = seg.max_right(0, [&](int x) { return x < A[i]; });
    int r = seg.max_right(0, [&](int x) { return x < A[i] + 1; });
    child[i + N] = pii{idx[l], idx[r]};
    subtree[i + N] = subtree[idx[l]] + subtree[idx[r]];
    par[idx[l]] = i + N;
    par[idx[r]] = i + N;
    idx[l] = i + N;
    idx[r] = -1;
    seg.set(r, 0);
  }
  string PRS = "PRS";

  auto jankenWin = [&](int a, int b) -> int {
    if (a == b)
      return -1;
    if ((a - b + 3) % 3 == 2)
      return a;
    else
      return b;
  };
  auto dfs = [&](auto self, int v, array<ll, 3> cnt, ll &k,
                 string &res) -> int {
    if (child[v].first == -1) {
      // leaf
      rep(i, 3) {
        if (k <= cnt[i]) {
          res[v] = PRS[i];
          return i;
        } else {
          k -= cnt[i];
        }
      }
      assert(0);
    } else {
      auto [Lchild, Rchild] = child[v];
      // left
      array<ll, 3> cntL;
      rep(i, 3) {
        cntL[i] = min((i128)(cnt[i] + cnt[(i + 2) % 3]) *
                          safePow2(subtree[Rchild] - 1),
                      (i128)INFL);
      }
      int l = self(self, Lchild, cntL, k, res);
      // right
      array<ll, 3> cntR;
      rep(i, 3) {
        if (i == l)
          cntR[i] = 0;
        else
          cntR[i] = cnt[jankenWin(l, i)];
      }
      int r = self(self, Rchild, cntR, k, res);
      return jankenWin(l, r);
    }
  };

  string ans(N, 0);
  // R
  ll k = K;
  dfs(dfs, N * 2 - 2, array<ll, 3>{0, 1, 0}, k, ans);
  cout << ans << '\n';

  // P
  k = K;
  dfs(dfs, N * 2 - 2, array<ll, 3>{1, 0, 0}, k, ans);
  cout << ans << '\n';

  // S
  k = K;
  dfs(dfs, N * 2 - 2, array<ll, 3>{0, 0, 1}, k, ans);
  cout << ans << '\n';
}