結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー Shiny
提出日時 2026-04-18 00:36:18
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
実行時間 -
コード長 4,068 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 566 ms
コンパイル使用メモリ 20,956 KB
実行使用メモリ 34,588 KB
最終ジャッジ日時 2026-04-18 00:37:29
合計ジャッジ時間 12,934 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

LIMIT = 10 ** 18 + 1

# 0=R, 1=P, 2=S
beat = [2, 0, 1]
lex_order = [1, 0, 2]  # P < R < S
ch = "RPS"

win = [[-1] * 3 for _ in range(3)]
for i in range(3):
    for j in range(3):
        if i != j:
            win[i][j] = i if beat[i] == j else j


def cap_add(a, b):
    s = a + b
    return LIMIT if s > LIMIT else s


def cap_mul(a, b):
    if a == 0 or b == 0:
        return 0
    if a > LIMIT // b:
        return LIMIT
    return a * b


class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, idx, val):
        idx += 1
        while idx <= self.n:
            self.bit[idx] += val
            idx += idx & -idx

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


def solve_case(n, k, a):
    size = 2 * n - 1
    left = [-1] * size
    right = [-1] * size

    bit = Fenwick(n)
    now = list(range(n))
    for i in range(n):
        bit.add(i, 1)

    node = n
    for pos in a:
        x = bit.kth(pos)
        y = bit.kth(pos + 1)
        left[node] = now[x]
        right[node] = now[y]
        now[x] = node
        bit.add(y, -1)
        node += 1
    root = node - 1

    ways = [[0, 0, 0] for _ in range(size)]
    for i in range(n):
        ways[i] = [1, 1, 1]

    for v in range(n, size):
        l = left[v]
        r = right[v]
        for c in range(3):
            d = beat[c]
            ways[v][c] = cap_add(
                cap_mul(ways[l][c], ways[r][d]),
                cap_mul(ways[l][d], ways[r][c])
            )

    def restore(target):
        if ways[root][target] < k:
            return "-1"

        out = ['?'] * n
        last_color = -1
        last_k = 0
        stack = [(0, root, [1 if i == target else 0 for i in range(3)], k, -1)]

        while stack:
            stage, v, weight, cur_k, extra = stack.pop()

            if stage == 0:
                if v < n:
                    rem = cur_k
                    for c in lex_order:
                        if rem > weight[c]:
                            rem -= weight[c]
                        else:
                            out[v] = ch[c]
                            last_color = c
                            last_k = rem
                            break
                    continue

                l = left[v]
                r = right[v]
                left_weight = [0, 0, 0]
                for x in range(3):
                    total = 0
                    for y in range(3):
                        if x == y:
                            continue
                        total = cap_add(total, cap_mul(ways[r][y], weight[win[x][y]]))
                    left_weight[x] = total

                stack.append((1, v, weight, cur_k, -1))
                stack.append((0, l, left_weight, cur_k, -1))

            elif stage == 1:
                left_color = last_color
                rem = last_k
                r = right[v]
                right_weight = [0, 0, 0]
                for y in range(3):
                    if y != left_color:
                        right_weight[y] = weight[win[left_color][y]]

                stack.append((2, v, weight, rem, left_color))
                stack.append((0, r, right_weight, rem, -1))

            else:
                left_color = extra
                right_color = last_color
                last_color = win[left_color][right_color]

        return ''.join(out)

    return [restore(0), restore(1), restore(2)]


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    t = data[0]
    idx = 1
    out = []

    for _ in range(t):
        n = data[idx]
        k = data[idx + 1]
        idx += 2
        a = data[idx:idx + n - 1]
        idx += n - 1

        out.extend(solve_case(n, k, a))

    sys.stdout.write('\n'.join(out))


if __name__ == '__main__':
    main()
0