結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 Shiny
|
| 提出日時 | 2026-04-18 00:41:50 |
| 言語 | Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 5,706 bytes |
| 記録 | |
| コンパイル時間 | 611 ms |
| コンパイル使用メモリ | 20,828 KB |
| 実行使用メモリ | 59,148 KB |
| 最終ジャッジ日時 | 2026-04-18 00:43:18 |
| 合計ジャッジ時間 | 15,536 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | AC * 5 TLE * 2 -- * 21 |
ソースコード
import sys
LIMIT = 10 ** 18 + 1
class Fenwick:
__slots__ = ("n", "bit")
def __init__(self, n):
self.n = n
self.bit = [0] * (n + 1)
def add(self, idx, val):
idx += 1
bit = self.bit
n = self.n
while idx <= n:
bit[idx] += val
idx += idx & -idx
def kth(self, k):
idx = 0
bit = self.bit
n = self.n
step = 1 << (n.bit_length() - 1)
while step:
nxt = idx + step
if nxt <= n and bit[nxt] < k:
idx = nxt
k -= bit[nxt]
step >>= 1
return idx
def solve_case(n, k, a):
size = 2 * n - 1
left = [0] * size
right = [0] * size
bit = Fenwick(n)
alive = 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] = alive[x]
right[node] = alive[y]
alive[x] = node
bit.add(y, -1)
node += 1
root = size - 1
# c0 = winner R count, c1 = winner P count, c2 = winner S count
c0 = [1] * size
c1 = [1] * size
c2 = [1] * size
lim = LIMIT
for v in range(n, size):
l = left[v]
r = right[v]
x0 = c0[l] * c2[r] + c2[l] * c0[r] # R
x1 = c1[l] * c0[r] + c0[l] * c1[r] # P
x2 = c2[l] * c1[r] + c1[l] * c2[r] # S
c0[v] = lim if x0 > lim else x0
c1[v] = lim if x1 > lim else x1
c2[v] = lim if x2 > lim else x2
def restore(target):
total = c0[root] if target == 0 else c1[root] if target == 1 else c2[root]
if total < k:
return "-1"
out = ['?'] * n
# 병렬 스택
sv = [root]
ss = [0]
sk = [k]
sw0 = [1 if target == 0 else 0]
sw1 = [1 if target == 1 else 0]
sw2 = [1 if target == 2 else 0]
sex = [-1]
last_color = -1
last_k = 0
while sv:
v = sv.pop()
stage = ss.pop()
cur_k = sk.pop()
w0 = sw0.pop()
w1 = sw1.pop()
w2 = sw2.pop()
extra = sex.pop()
if stage == 0:
if v < n:
rem = cur_k
# 사전순: P < R < S
if rem <= w1:
out[v] = 'P'
last_color = 1
last_k = rem
else:
rem -= w1
if rem <= w0:
out[v] = 'R'
last_color = 0
last_k = rem
else:
out[v] = 'S'
last_color = 2
last_k = rem - w0
continue
l = left[v]
r = right[v]
rc0 = c0[r]
rc1 = c1[r]
rc2 = c2[r]
# left subtree에 대해 각 최종 색을 선택했을 때 가능한 경우의 수
lw0 = rc2 * w0 + rc1 * w1
lw1 = rc0 * w1 + rc2 * w2
lw2 = rc1 * w2 + rc0 * w0
if lw0 > lim:
lw0 = lim
if lw1 > lim:
lw1 = lim
if lw2 > lim:
lw2 = lim
sv.append(v)
ss.append(1)
sk.append(cur_k)
sw0.append(w0)
sw1.append(w1)
sw2.append(w2)
sex.append(-1)
sv.append(l)
ss.append(0)
sk.append(cur_k)
sw0.append(lw0)
sw1.append(lw1)
sw2.append(lw2)
sex.append(-1)
elif stage == 1:
lc = last_color
rem = last_k
# 왼쪽 색이 정해졌을 때 오른쪽 가중치
if lc == 0: # R
rw0 = 0
rw1 = w1
rw2 = w0
elif lc == 1: # P
rw0 = w1
rw1 = 0
rw2 = w2
else: # S
rw0 = w0
rw1 = w2
rw2 = 0
sv.append(v)
ss.append(2)
sk.append(rem)
sw0.append(w0)
sw1.append(w1)
sw2.append(w2)
sex.append(lc)
r = right[v]
sv.append(r)
ss.append(0)
sk.append(rem)
sw0.append(rw0)
sw1.append(rw1)
sw2.append(rw2)
sex.append(-1)
else:
lc = extra
rc = last_color
# 최종 winner 계산
if lc == 0: # R
last_color = 0 if rc == 2 else 1
elif lc == 1: # P
last_color = 1 if rc == 0 else 2
else: # S
last_color = 2 if rc == 1 else 0
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()