結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー tassei903
提出日時 2026-04-19 21:07:59
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 2,973 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 122 ms
コンパイル使用メモリ 85,156 KB
実行使用メモリ 134,824 KB
最終ジャッジ日時 2026-04-19 21:08:38
合計ジャッジ時間 7,461 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#####################################################################

"""
012
f(0, 1) = 1
f(1, 2) = 2
f(2, 0) = 0

N = 2
0: 02 20
1: 01 10
2: 12 21

N = 3 (0, 0)
0: 022 120 210 202, 012 021 2

N = 4

f(S) = 0となる S の個数 2 ** (N - 1)
これは，逆に構築するとできる

A[i] = 0 となる 最小の i をとる
S[0] = 0 となる個数は 1* -> 01, 0* -> 02

S[0] = 0 で f(S) = 0となる S の個数 2 ** (N - 1) 

3 * 2 ** (N - 1)



再帰的にやるなら，A[n-1] が

f(S[:i], n)

P R S
0 1 2
f(0, 1) = 0
f(1, 2) = 1
f(2, 0) = 2

"""


def solve(n, k, a):
    if n <= 100 and k >= 2 ** (n - 1):
        return
    def ff(x, y):
        if x == (y - 1) % 3:
            return x
        else:
            return y
            
    def saiki(pre, n, x):
        # print(pre, n, x)
        if n == 1:
            return int(pre[0] == x)
        
        if len(pre) <= a[n-2]:
            return saiki(pre, n-1, x) * 2
        elif len(pre) == a[n-2] + 1:
            return saiki(pre[:a[n-2]] + (pre[a[n-2]], ), n-1, x) + saiki(pre[:a[n-2]] + ((pre[a[n-2]] - 1) % 3, ), n-1, x)
        elif pre[a[n-2]] != pre[a[n-2] + 1]:
            return saiki(pre[:a[n-2]] + (ff(pre[a[n-2]], pre[a[n-2] + 1]), ) + pre[a[n-2]+2:], n - 1, x)
        else:
            return 0
    
    res = []
    for x in [1, 0, 2]:
        ans = []
        K = k
        for i in range(n):
            for j in range(3):
                z = saiki(tuple(ans) + (j,), n, x)
                # print(tuple(ans + [j]), z, a, x)
                if K - z >= 0:
                    K -= z
                else:
                    ans.append(j)
                    break
        res.append(ans)
    #     print()
    # print()

    return res
def naive(n, k, a):
    if k >= 2 ** (n - 1):
        return
    
    ans = []

    for t in [1, 0, 2]:
        res = [tuple([t])]
        for i in range(n-1):
            nres = []
            for p in res:
                x, y = sorted([p[a[i]], (p[a[i]] + 1) % 3])
                nres.append(p[:a[i]] + (x, y) + p[a[i]+1:])
                nres.append(p[:a[i]] + (y, x) + p[a[i]+1:])
            res = nres
        for i in sorted(res):
            # put(i)
            print(i)
        print()
        idx = sorted(range(len(res)), key = lambda i: res[i])
        # print(idx)
        
        ans.append(sorted(res)[k])
                

def put(ans):
    print("".join(["PRS"[i] for i in ans]))


# naive(5, 0, [0, 1, 1, 3])


for _ in range(ni()):
    n, k = na()
    k -= 1
    a = [x-1 for x in na()][::-1]
    res = solve(n, k, a)
    if res is None:
        for i in range(3):
            print(-1)
    else:
        for i in res:
            # print(i)
            put(i)
        # print()
0