#1158601 (Python3) No.3510 RPS Eliminations

• 問題: No.3510 RPS Eliminations
• ユーザー: Shiny
• 提出日時: 2026-04-18 00:24:31
• 言語: Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1)
• 結果: TLE
• 実行時間: -
• コード長: 3,654 bytes
• コンパイル時間: 577 ms
• コンパイル使用メモリ: 20,824 KB
• 実行使用メモリ: 89,272 KB
• 最終ジャッジ日時: 2026-04-18 00:25:24
• 合計ジャッジ時間: 13,479 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_1

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

ソースコード

import sys

input = sys.stdin.readline
LIMIT = 10 ** 18 + 1
NO_ANS = "None"   # 원문 no-answer 표기에 맞게 바꾸면 됩니다.

# 내부 인덱스: 0=R, 1=P, 2=S
beat = [2, 0, 1]          # beat[x] = x가 이기는 문자
lex_order = [1, 0, 2]     # P < R < S
ch = "RPS"

win = [[-1] * 3 for _ in range(3)]
for i in range(3):
    for j in range(3):
        if i == j:
            continue
        win[i][j] = i if beat[i] == j else j


def cap_mul(a, b):
    if a == 0 or b == 0:
        return 0
    if a > LIMIT // b:
        return LIMIT
    return a * b


def cap_add(a, b):
    s = a + b
    return LIMIT if s > LIMIT else s


class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, idx, val):
        idx += 1
        while idx <= self.n:
            self.bit[idx] += val
            idx += idx & -idx

    def kth(self, k):
        idx = 0
        step = 1 << (self.n.bit_length() - 1)
        while step:
            nxt = idx + step
            if nxt <= self.n and self.bit[nxt] < k:
                k -= self.bit[nxt]
                idx = nxt
            step >>= 1
        return idx


def solve_case(n, k, a):
    size = 2 * n - 1
    left = [-1] * size
    right = [-1] * size

    bit = Fenwick(n)
    where = list(range(n))
    for i in range(n):
        bit.add(i, 1)

    node = n
    for pos in a:
        x = bit.kth(pos)
        y = bit.kth(pos + 1)
        left[node] = where[x]
        right[node] = where[y]
        where[x] = node
        bit.add(y, -1)
        node += 1

    root = node - 1

    ways = [[0, 0, 0] for _ in range(size)]
    for i in range(n):
        ways[i] = [1, 1, 1]

    for v in range(n, size):
        l = left[v]
        r = right[v]
        for c in range(3):
            d = beat[c]
            val = cap_add(cap_mul(ways[l][c], ways[r][d]),
                          cap_mul(ways[l][d], ways[r][c]))
            ways[v][c] = val

    sys.setrecursionlimit(1_000_000)

    def build(v, weight, kth, out):
        if v < n:
            for c in lex_order:
                if kth > weight[c]:
                    kth -= weight[c]
                else:
                    out[v] = ch[c]
                    return c, kth
            raise RuntimeError("unreachable")

        l = left[v]
        r = right[v]

        left_weight = [0, 0, 0]
        for x in range(3):
            total = 0
            for y in range(3):
                if x == y:
                    continue
                total = cap_add(total, cap_mul(ways[r][y], weight[win[x][y]]))
            left_weight[x] = total

        left_color, rem = build(l, left_weight, kth, out)

        right_weight = [0, 0, 0]
        for y in range(3):
            if y != left_color:
                right_weight[y] = weight[win[left_color][y]]

        right_color, rem = build(r, right_weight, rem, out)
        return win[left_color][right_color], rem

    ans = []
    for target in (0, 1, 2):   # R, P, S 순서
        if ways[root][target] < k:
            ans.append(NO_ANS)
            continue
        out = ['?'] * n
        build(root, [1 if i == target else 0 for i in range(3)], k, out)
        ans.append(''.join(out))

    return ans


def solve():
    t = int(input())
    out_lines = []
    for _ in range(t):
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        cur = solve_case(n, k, a)
        out_lines.append(' '.join(cur))
        # 원문이 3줄 출력이면 위 한 줄 대신 아래를 쓰면 됩니다.
        # out_lines.extend(cur)
    print('\n'.join(out_lines))


if __name__ == "__main__":
    solve()