結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー e032_Ashmit_Rana
提出日時 2026-04-18 01:43:34
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 2,064 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 490 ms
コンパイル使用メモリ 20,828 KB
実行使用メモリ 88,316 KB
最終ジャッジ日時 2026-04-18 01:44:23
合計ジャッジ時間 48,165 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 14 RE * 6 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

INF = 10**18

# R=0, P=1, S=2
def solve():
    T = int(input())
    for _ in range(T):
        N, K = map(int, input().split())
        A = list(map(int, input().split()))

        # --- Build tree ---
        left = [-1] * (2 * N)
        right = [-1] * (2 * N)

        nodes = list(range(N))  # current active nodes
        ptr = N  # next new node index

        for i in range(N - 1):
            a = A[i] - 1
            L = nodes[a]
            R = nodes[a + 1]
            left[ptr] = L
            right[ptr] = R
            # replace two nodes with new node
            nodes[a:a+2] = [ptr]
            ptr += 1

        root = nodes[0]

        # --- DP counts ---
        cnt = [[0, 0, 0] for _ in range(ptr)]

        def dfs(u):
            if left[u] == -1:
                cnt[u] = [1, 1, 1]
                return
            dfs(left[u])
            dfs(right[u])

            L, R = left[u], right[u]

            # R: (R, S)
            cnt[u][0] = min(INF, cnt[L][0] * cnt[R][2])
            # P: (P, R)
            cnt[u][1] = min(INF, cnt[L][1] * cnt[R][0])
            # S: (S, P)
            cnt[u][2] = min(INF, cnt[L][2] * cnt[R][1])

        dfs(root)

        # --- reconstruction ---
        def build(u, target, k):
            if left[u] == -1:
                return "RPS"[target]

            L, R = left[u], right[u]

            if target == 0:      # R
                tL, tR = 0, 2
            elif target == 1:    # P
                tL, tR = 1, 0
            else:                # S
                tL, tR = 2, 1

            right_count = cnt[R][tR]

            # determine indices
            left_index = (k - 1) // right_count + 1
            right_index = (k - 1) % right_count + 1

            return build(L, tL, left_index) + build(R, tR, right_index)

        # --- output for R, P, S ---
        for t in range(3):
            if cnt[root][t] < K:
                print(-1)
            else:
                print(build(root, t, K))


if __name__ == "__main__":
    solve()
0