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

• 問題: No.3510 RPS Eliminations
• ユーザー: Nzt3
• 提出日時: 2026-04-06 15:32:32
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 7,622 bytes
• コンパイル時間: 2,655 ms
• コンパイル使用メモリ: 345,352 KB
• 実行使用メモリ: 29,132 KB
• 最終ジャッジ日時: 2026-04-17 20:06:28
• 合計ジャッジ時間: 23,846 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	-- * 1
other	AC * 20 TLE * 1 -- * 7

ソースコード

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>


#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#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 per(i, a, b) for (ll i = (a) - 1; i >= (b); i--)
#define fore(e, v) for (auto &&e : v)
#define all(a) begin(a), end(a)
#define sz(a) (int)(size(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

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 safeMul = [&](ll a, ll b) -> ll {
    return (ll)min((i128)INFL, (i128)a * b);
  };

  auto ans = [&](int target) -> string {
    string res(N, '/');
    vector<array<ll, 3>> dp(N * 2);
    rep(i, N) { rep(j, 3) dp[i][j] = 0; }
    ll c = K;
    rep(i, N) {
      bool ok = 0;
      rep(j, 3) {
        array<ll, 3> cnt;
        rep(k, 3) cnt[k] = k == j;
        int v = i;
        while (par[v] != -1) {
          array<ll, 3> cnt2;
          rep(k, 3) cnt2[k] = 0;
          int p = par[v];
          dp[v] = cnt;
          if (v == child[p].first) {
            rep(a, 3) {
              rep(b, 3) {
                if (a != b)
                  cnt2[jankenWin(a, b)] +=
                      safeMul(cnt[a], safePow2(subtree[child[p].second] - 1));
              }
            }
          } else {
            rep(a, 3) {
              rep(b, 3) {
                if (a != b)
                  cnt2[jankenWin(a, b)] +=
                      safeMul(cnt[a], dp[child[p].first][b]);
              }
            }
          }
          rep(a, 3) chmin(cnt2[a], INFL);
          cnt = cnt2;
          v = p;
        }
        if (cnt[target] >= c) {
          res[i] = PRS[j];
          ok = 1;
          break;
        } else {
          c -= cnt[target];
        }
      }
      if (!ok)
        return "-1";
    }
    return res;
  };

  cout << ans(1) << '\n';
  cout << ans(0) << '\n';
  cout << ans(2) << '\n';
}