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

• 問題: No.3510 RPS Eliminations
• ユーザー: Enderaoe Lyther
• 提出日時: 2026-04-17 22:10:04
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,801 bytes
• コンパイル時間: 2,215 ms
• コンパイル使用メモリ: 186,364 KB
• 実行使用メモリ: 19,648 KB
• 最終ジャッジ日時: 2026-04-17 22:10:38
• 合計ジャッジ時間: 8,564 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

using u64 = unsigned long long;
using u128 = __uint128_t;

static inline char loser(char w) {
  if (w == 'R')
    return 'S';
  if (w == 'P')
    return 'R';
  return 'P';
}

struct Nat {
  bool inf;
  u64 v;
  static Nat from_rem(int rem) {
    if (rem < 0)
      return {false, 0};
    if (rem >= 62)
      return {true, 0};
    return {false, 1ULL << rem};
  }
  bool is_zero() const { return !inf && v == 0; }
  Nat minus(u64 pa) const {
    if (inf)
      return *this;
    return {false, v - pa};
  }
};

static u128 subtree_leaves_u128(int rem) {
  if (rem <= 0)
    return 1;
  if (rem >= 127)
    return (u128)1 << 126;
  return (u128)1 << rem;
}

static bool k_too_large(u64 K, int nm1) {
  u128 cnt = subtree_leaves_u128(nm1);
  return (u128)K > cnt;
}

static std::vector<char> expand(const std::vector<int> &A, int N,
                                const std::vector<char> &cur, int depth,
                                int side) {
  int t = N - 2 - depth;
  int p = A[t] - 1;
  std::vector<char> ncur = cur;
  if (side == 0) {
    char w = ncur[p];
    ncur.insert(ncur.begin() + p + 1, loser(w));
  } else {
    char win = ncur[p];
    ncur.insert(ncur.begin() + p, loser(win));
  }
  return ncur;
}

static std::string kth_in_subtree(const std::vector<int> &A, int N,
                                  const std::vector<char> &cur, int depth,
                                  u64 k);

static std::string kth_merge_nat(Nat na, u64 loA, Nat nb, u64 loB, u64 k,
                                 const std::function<std::string(u64)> &getA,
                                 const std::function<std::string(u64)> &getB) {
  if (na.is_zero())
    return getB(loB + k);
  if (nb.is_zero())
    return getA(loA + k);
  if (k == 0) {
    std::string sa = getA(loA);
    std::string sb = getB(loB);
    return std::min(sa, sb);
  }

  bool swap = false;
  if (na.inf != nb.inf) {
    if (na.inf && !nb.inf)
      swap = true;
  } else if (!na.inf && !nb.inf) {
    if (na.v > nb.v)
      swap = true;
  }

  if (swap) {
    return kth_merge_nat(nb, loB, na, loA, k, getB, getA);
  }

  u64 pa;
  if (na.inf)
    pa = (k + 1) / 2;
  else
    pa = std::min<u64>(na.v, (k + 1) / 2);

  u64 pb = k + 1 - pa;
  if (!nb.inf && pb > nb.v) {
    pb = nb.v;
    pa = k + 1 - pb;
  }

  std::string a_mid = getA(loA + pa - 1);
  std::string b_mid = getB(loB + pb - 1);
  if (a_mid < b_mid)
    return kth_merge_nat(na.minus(pa), loA + pa, nb, loB, k - pa, getA, getB);
  return kth_merge_nat(na, loA, nb.minus(pb), loB + pb, k - pb, getA, getB);
}

static std::string kth_in_subtree(const std::vector<int> &A, int N,
                                  const std::vector<char> &cur, int depth,
                                  u64 k) {
  if (depth == N - 1)
    return std::string(cur.begin(), cur.end());
  auto L = expand(A, N, cur, depth, 0);
  auto R = expand(A, N, cur, depth, 1);
  int nd = depth + 1;
  int rem = N - 1 - nd;
  Nat nlen = Nat::from_rem(rem);
  auto getL = [&](u64 idx) { return kth_in_subtree(A, N, L, nd, idx); };
  auto getR = [&](u64 idx) { return kth_in_subtree(A, N, R, nd, idx); };
  return kth_merge_nat(nlen, 0, nlen, 0, k, getL, getR);
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int T;
  std::cin >> T;
  while (T--) {
    int N;
    u64 K;
    std::cin >> N >> K;
    std::vector<int> A(N - 1);
    for (int i = 0; i < N - 1; ++i)
      std::cin >> A[i];
    for (char fin : {'R', 'P', 'S'}) {
      if (k_too_large(K, N - 1)) {
        std::cout << -1 << '\n';
        continue;
      }
      std::vector<char> start{fin};
      std::cout << kth_in_subtree(A, N, start, 0, K - 1) << '\n';
    }
  }
  return 0;
}