#1159478 (Python3) No.3510 RPS Eliminations

• 問題: No.3510 RPS Eliminations
• ユーザー: 왕지후
• 提出日時: 2026-04-18 11:53:54
• 言語: Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1)
• 結果: TLE
• 実行時間: -
• コード長: 5,331 bytes
• コンパイル時間: 720 ms
• コンパイル使用メモリ: 20,700 KB
• 実行使用メモリ: 65,232 KB
• 最終ジャッジ日時: 2026-04-18 11:55:10
• 合計ジャッジ時間: 15,318 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
sample	-- * 1
other	AC * 5 TLE * 1 -- * 22

ソースコード

import sys

def solve():
    # Read all inputs from standard input at once
    input_data = sys.stdin.read().split()
    if not input_data:
        return
        
    T = int(input_data[0])
    idx = 1
    
    INF = 10**18 + 1
    out_lines = []
    
    # Pre-allocate global arrays once to avoid TLE from memory reallocation
    MAX_NODES = 400005
    bit = [0] * MAX_NODES
    pos_id = [0] * MAX_NODES
    L = [0] * MAX_NODES
    R = [0] * MAX_NODES
    sz = [0] * MAX_NODES
    ret = [''] * MAX_NODES
    ans = [''] * MAX_NODES
    
    for _ in range(T):
        N = int(input_data[idx])
        K = int(input_data[idx+1])
        idx += 2
        
        # If K exceeds total possible combinations
        if N - 1 < 60 and K > (1 << (N - 1)):
            out_lines.extend(["-1", "-1", "-1"])
            idx += N - 1
            continue
            
        # Dynamically find the highest bit needed for Fenwick operations
        max_bit = 0
        while (1 << max_bit) <= N:
            max_bit += 1
        max_bit -= 1
        bits_range = tuple(range(max_bit, -1, -1))
        
        # Initialize only up to N for the current test case
        for i in range(1, N + 1):
            bit[i] = i & (-i)
            pos_id[i] = i
            sz[i] = 1
            
        # Fast iterative tree construction
        for i in range(1, N):
            A_val = int(input_data[idx])
            idx += 1
            
            # Find idx1
            k_val = A_val
            pos = 0
            for j in bits_range:
                nxt = pos + (1 << j)
                if nxt <= N and bit[nxt] < k_val:
                    pos = nxt
                    k_val -= bit[nxt]
            idx1 = pos + 1
            
            # Find idx2
            k_val = A_val + 1
            pos = 0
            for j in bits_range:
                nxt = pos + (1 << j)
                if nxt <= N and bit[nxt] < k_val:
                    pos = nxt
                    k_val -= bit[nxt]
            idx2 = pos + 1
            
            u = pos_id[idx1]
            v = pos_id[idx2]
            
            node = N + i
            L[node] = u
            R[node] = v
            sz[node] = sz[u] + sz[v]
            
            pos_id[idx1] = node
            
            # Inline BIT add logic for idx2 (-1)
            curr = idx2
            while curr <= N:
                bit[curr] -= 1
                curr += curr & (-curr)
                
        root = 2 * N - 1
        
        for target in ('R', 'P', 'S'):
            K_cur = K
            oR = 1 if target == 'R' else 0
            oP = 1 if target == 'P' else 0
            oS = 1 if target == 'S' else 0
            
            # State-machine stack: [node, oR, oP, oS, state]
            stack = [[root, oR, oP, oS, 0]]
            
            while stack:
                frame = stack[-1]
                u = frame[0]
                state = frame[4]
                
                # Leaf node base case
                if u <= N:
                    for c in ('P', 'R', 'S'):
                        ways = frame[2] if c == 'P' else (frame[1] if c == 'R' else frame[3])
                        if K_cur <= ways:
                            ans[u] = c
                            ret[u] = c
                            break
                        else:
                            K_cur -= ways
                    stack.pop()
                    continue
                    
                if state == 0:
                    frame[4] = 1
                    lc = L[u]
                    rc = R[u]
                    k = sz[rc] - 1
                    mult = (1 << k) if k < 60 else INF
                    
                    nR = mult * (frame[1] + frame[2])
                    nP = mult * (frame[2] + frame[3])
                    nS = mult * (frame[3] + frame[1])
                    
                    if nR > INF: nR = INF
                    if nP > INF: nP = INF
                    if nS > INF: nS = INF
                    
                    stack.append([lc, nR, nP, nS, 0])
                    
                elif state == 1:
                    frame[4] = 2
                    lc = L[u]
                    rc = R[u]
                    vL = ret[lc]
                    
                    if vL == 'S':
                        n2R, n2P, n2S = frame[1], frame[3], 0
                    elif vL == 'P':
                        n2R, n2P, n2S = frame[2], 0, frame[3]
                    else:
                        n2R, n2P, n2S = 0, frame[2], frame[1]
                        
                    stack.append([rc, n2R, n2P, n2S, 0])
                    
                else: # State == 2 (Returning from both branches)
                    lc = L[u]
                    rc = R[u]
                    vL = ret[lc]
                    vR = ret[rc]
                    
                    if (vL == 'R' and vR == 'S') or (vL == 'S' and vR == 'R'): ret[u] = 'R'
                    elif (vL == 'P' and vR == 'R') or (vL == 'R' and vR == 'P'): ret[u] = 'P'
                    else: ret[u] = 'S'
                    
                    stack.pop()
                    
            out_lines.append("".join(ans[1:N+1]))
            
    sys.stdout.write("\n".join(out_lines) + "\n")

if __name__ == '__main__':
    solve()