#1160718 (PyPy3) No.3510 RPS Eliminations

• 問題: No.3510 RPS Eliminations
• ユーザー: tassei903
• 提出日時: 2026-04-20 01:26:22
• 言語: PyPy3 (7.3.17)
• 結果: AC
• 実行時間: 604 ms / 2,000 ms
• コード長: 4,244 bytes
• コンパイル時間: 180 ms
• コンパイル使用メモリ: 85,120 KB
• 実行使用メモリ: 275,700 KB
• 最終ジャッジ日時: 2026-04-20 01:26:47
• 合計ジャッジ時間: 17,825 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 28

ソースコード

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")

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        assert 0 <= i < self.n
        i = i+1
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def set(self, i, x):
        assert 0 <= i <= self.n
        self.add(i,x-self.get(i))
    def get(self, i, j):
        return self.sum(j) - self.sum(i)
    def lower_bound(self, k):
        n = self.n
        x = 0
        r = 1
        while r <= n:r <<= 1
        size = r
        while size:
            if x + size <= n and self.data[x+size] <= k:
                k-=self.data[x+size]
                x += size
            size >>= 1
        return x
    def debug(self):
        res = []
        n = self.n
        for i in range(n):
            res.append(self.get(i))
        print(*res)                

lim = 10 ** 18 + 100

def solve(n, k, a):
    if n <= 64 and k >= 2 ** (n - 1):
        return
    bit = BIT(n)

    for i in range(n):
        bit.add(i, 1)
    par = [-1] * n
    now = [i for i in range(n)]
    l = [-1] * (n * 2 - 1)
    r = [-1] * (n * 2 - 1)
    sub = [1] * n    
    for i in range(n-2, -1, -1):
        y = bit.lower_bound(a[i])
        z = bit.lower_bound(a[i] + 1)
        bit.add(z, -1)
        par[now[y]] = len(par)
        par[now[z]] = len(par)
        l[len(par)] = now[y]
        r[len(par)] = now[z]
        sub.append(sub[now[y]] + sub[now[z]])
        now[y] = len(par)
        par.append(-1)

    res = []
    def janken(x, y):
        if x == (y - 1) % 3:
            return x
        else:
            return y
    
    for x in [1, 0, 2]:
        ans = []
        
        local_q = [0] * (n * 2 - 1)
        local_fl = [0] * (n * 2 - 1)
        
        z = [0, 0, 0]
        z[x] = 1
        
        stack = [(n * 2 - 2, k, tuple(z), 0)]
        
        ret_fl = -1
        ret_rest = -1
        
        while stack:
            id, cur_k, g, step = stack.pop()
            
            if step == 0:
                if id < n:
                    for i in range(3):
                        if cur_k - g[i] >= 0:
                            cur_k -= g[i]
                        else:
                            ans.append(i)
                            ret_fl, ret_rest = i, cur_k
                            break
                    continue
                
                if sub[r[id]] >= 65:
                    p, q = 0, cur_k
                else:
                    p, q = divmod(cur_k, 1 << (sub[r[id]] - 1))
                
                local_q[id] = q
                
                stack.append((id, cur_k, g, 1))
                
                g_new = (min(lim, g[2] + g[0]), min(lim, g[0] + g[1]), min(lim, g[1] + g[2]))
                stack.append((l[id], p, g_new, 0))
                
            elif step == 1:
                fl = ret_fl
                rest = ret_rest
                local_fl[id] = fl
                
                z_new = [0, 0, 0]
                z_new[(fl - 1) % 3] = g[(fl - 1) % 3]
                z_new[(fl + 1) % 3] = g[fl]
                
                stack.append((id, cur_k, g, 2))
                
                q = local_q[id]
                next_k = (rest << (sub[r[id]] - 1)) + q
                stack.append((r[id], next_k, tuple(z_new), 0))
                
            elif step == 2:
                fr = ret_fl
                rest = ret_rest
                fl = local_fl[id]
                
                ret_fl = janken(fl, fr)
                ret_rest = rest

        res.append(ans)

    return res

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

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:
            put(i)