結果

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

ソースコード

diff #
raw source code 

import sys
sys.setrecursionlimit(200010)
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
        now = k
        ok = True

        def dfs(u, mat):
            nonlocal now, ok

            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:
                    ok = False
                    return -1
                return sel

            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]
                        if addv >= k:
                            addv = k
                        C[i][j] += addv
                        if C[i][j] >= k:
                            C[i][j] = k

            lv = dfs(l[u], C)
            if not ok:
                return -1

            vec = [0,0,0]
            vec[lv] = 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]
                        if addv >= k:
                            addv = k
                        C[i][j] += addv
                        if C[i][j] >= k:
                            C[i][j] = k

            rv = dfs(r[u], C)
            if not ok:
                return -1

            if lv == rv:
                return -1
            if rv == (lv + 1) % 3:
                return lv
            return rv

        ret = dfs(root, [[1,0,0],[0,1,0],[0,0,1]])

        if (not ok) or ret == -1 and n == 1 and ans[0] == '':
            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