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

• 問題: No.3510 RPS Eliminations
• ユーザー: Enderaoe Lyther
• 提出日時: 2026-04-17 22:15:11
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,956 bytes
• コンパイル時間: 2,270 ms
• コンパイル使用メモリ: 223,992 KB
• 実行使用メモリ: 197,760 KB
• 最終ジャッジ日時: 2026-04-17 22:15:54
• 合計ジャッジ時間: 9,360 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <map>
#include <string>
#include <tuple>
#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::map<std::tuple<int, std::string, u64>, std::string> memo_kth;

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) {
  std::string ck(cur.begin(), cur.end());
  auto key = std::make_tuple(depth, ck, k);
  auto it = memo_kth.find(key);
  if (it != memo_kth.end())
    return it->second;

  std::string res;
  if (depth == N - 1) {
    res = ck;
  } else {
    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); };
    res = kth_merge_nat(nlen, 0, nlen, 0, k, getL, getR);
  }
  memo_kth.emplace(std::move(key), res);
  return res;
}

static void gen_all_dfs(const std::vector<int> &A, int N, std::vector<char> cur,
                        int depth, std::vector<std::string> &out) {
  if (depth == N - 1) {
    out.emplace_back(cur.begin(), cur.end());
    return;
  }
  for (int side : {0, 1}) {
    gen_all_dfs(A, N, expand(A, N, cur, depth, side), depth + 1, out);
  }
}

static std::string kth_by_enumerate(const std::vector<int> &A, int N, char fin,
                                    u64 k) {
  std::vector<std::string> all;
  gen_all_dfs(A, N, std::vector<char>{fin}, 0, all);
  std::sort(all.begin(), all.end());
  return all[k - 1];
}

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];

    const int nm1 = N - 1;
    const bool use_enum = nm1 <= 22;

    for (char fin : {'R', 'P', 'S'}) {
      if (k_too_large(K, nm1)) {
        std::cout << -1 << '\n';
        continue;
      }
      if (use_enum) {
        std::cout << kth_by_enumerate(A, N, fin, K) << '\n';
      } else {
        memo_kth.clear();
        std::vector<char> start{fin};
        std::cout << kth_in_subtree(A, N, start, 0, K - 1) << '\n';
      }
    }
  }
  return 0;
}