結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー Naru820
提出日時 2026-04-01 10:18:57
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 4,562 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 430 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 313,432 KB
最終ジャッジ日時 2026-04-17 19:57:04
合計ジャッジ時間 37,714 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 21 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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


def solve(n,k,a):
    # 木をまず作る
    l = [-1] * (2 * n - 1)
    r = [-1] * (2 * n - 1)
    sz = [1] * (2 * n - 1)
    pos = [-1] * (n + 1)
    bit = BIT(n)

    for i in range(1, n + 1):
        bit.add(i, 1)
        pos[i] = i - 1

    nx = n
    for x in a:
        p = bit.kth(x)
        q = bit.kth(x + 1)
        u = pos[p]
        v = pos[q]
        l[nx] = u
        r[nx] = v
        sz[nx] = sz[u] + sz[v]
        pos[p] = nx
        bit.add(q, -1)
        nx += 1

    root = 0 if n == 1 else pos[bit.kth(1)]

    res = []
    twopow = [1] * (n + 1)
    for i in range(1, n + 1):
        twopow[i] = min(k,twopow[i - 1] * 2)
        
    if twopow[n - 1] < k:
        print(-1)
        print(-1)
        print(-1)
        return
    
    for c in [1,0,2]:  # R,P,Sの順
        ans = [''] * n
        st = [[root, 0, [[1,0,0],[0,1,0],[0,0,1]], -2]]
        has_ret = False
        ret = -2
        now = k

        while st:
            u, state, mat, val = st.pop()

            if l[u] == -1:
                sel = -1
                for ch in range(3):
                    cnt = mat[c][ch]
                    if cnt >= now:
                        sel = ch
                        ans[u] = 'PRS'[ch]
                        break
                    now -= cnt
                if sel == -1:
                    ans = None
                    break
                ret = sel
                has_ret = True
                continue

            if state == 0:
                freecnt = twopow[sz[r[u]] - 1]
                M = [[0,0,0],[0,0,0],[0,0,0]]
                for cc in range(3):
                    lose = (cc + 1) % 3
                    M[cc][cc] = freecnt
                    M[cc][lose] = freecnt

                C = [[0,0,0],[0,0,0],[0,0,0]]
                for i in range(3):
                    for kk in range(3):
                        if mat[i][kk] == 0:
                            continue
                        for j in range(3):
                            if M[kk][j] == 0:
                                continue
                            addv = mat[i][kk] * M[kk][j]
                            C[i][j] += addv

                st.append([u, 1, mat, val])
                st.append([l[u], 0, C, -2])
                continue

            if state == 1:
                if has_ret:
                    val = ret
                    has_ret = False

                vec = [0,0,0]
                vec[val] = 1
                M = [[0,0,0],[0,0,0],[0,0,0]]
                for cc in range(3):
                    lose = (cc + 1) % 3
                    M[cc][cc] = vec[lose]
                    M[cc][lose] = vec[cc]

                C = [[0,0,0],[0,0,0],[0,0,0]]
                for i in range(3):
                    for kk in range(3):
                        if mat[i][kk] == 0:
                            continue
                        for j in range(3):
                            if M[kk][j] == 0:
                                continue
                            addv = mat[i][kk] * M[kk][j]
                            C[i][j] += addv

                st.append([u, 2, mat, val])
                st.append([r[u], 0, C, -2])
                continue

            if has_ret:
                vr = ret
                has_ret = False
                if val == vr:
                    ret = -1
                else:
                    if vr == (val + 1) % 3:
                        ret = val
                    else:
                        ret = vr
                has_ret = True
                continue

            ans = None
            break

        if ans is None:
            res.append(-1)
        else:
            res.append(''.join(ans))

    print(*res, sep='\n')


t = int(input())
while t > 0:
    t -= 1
    n,k = map(int, input().split())
    a = list(map(int, input().split()))
    solve(n,k,a)
0