結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 Naru820
|
| 提出日時 | 2026-04-01 10:29:29 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,425 bytes |
| 記録 | |
| コンパイル時間 | 290 ms |
| コンパイル使用メモリ | 84,864 KB |
| 実行使用メモリ | 254,264 KB |
| 最終ジャッジ日時 | 2026-04-17 19:57:57 |
| 合計ジャッジ時間 | 21,779 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | WA * 21 TLE * 1 -- * 6 |
ソースコード
import sys
sys.setrecursionlimit(1 << 20)
input = sys.stdin.readline
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):
tree = self.tree
size = self.size
while i <= size:
tree[i] += x
i += i & -i
def kth(self, k):
idx = 0
step = 1
size = self.size
tree = self.tree
while (step << 1) <= size:
step <<= 1
d = step
while d > 0:
nxt = idx + d
if nxt <= size and tree[nxt] < k:
idx = nxt
k -= 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)]
twopow = [1] * (n + 1)
for i in range(1, n + 1):
x = twopow[i - 1] << 1
twopow[i] = k if x >= k else x
if twopow[n - 1] < k:
print(-1)
print(-1)
print(-1)
return
res = []
lcl = l
rcl = r
szcl = sz
twoc = twopow
K = k
for c in (1, 0, 2): # R,P,Sの順
ans = [''] * n
now = k
ok = True
def dfs(u, a00, a01, a02, a10, a11, a12, a20, a21, a22):
nonlocal now, ok
if lcl[u] == -1:
if c == 0:
x0, x1, x2 = a00, a01, a02
elif c == 1:
x0, x1, x2 = a10, a11, a12
else:
x0, x1, x2 = a20, a21, a22
if x0 >= now:
ans[u] = 'P'
return 0
now -= x0
if x1 >= now:
ans[u] = 'R'
return 1
now -= x1
if x2 >= now:
ans[u] = 'S'
return 2
ok = False
return -1
# 右部分木が自由なときの変換
t = twoc[szcl[rcl[u]] - 1]
# M =
# [t t 0]
# [0 t t]
# [t 0 t]
#
# C = A * M
#
# 各列を直接計算
b00 = a00 * t
if b00 >= K: b00 = K
x = a02 * t
if x >= K: x = K
b00 += x
if b00 >= K: b00 = K
b01 = a00 * t
if b01 >= K: b01 = K
x = a01 * t
if x >= K: x = K
b01 += x
if b01 >= K: b01 = K
b02 = a01 * t
if b02 >= K: b02 = K
x = a02 * t
if x >= K: x = K
b02 += x
if b02 >= K: b02 = K
b10 = a10 * t
if b10 >= K: b10 = K
x = a12 * t
if x >= K: x = K
b10 += x
if b10 >= K: b10 = K
b11 = a10 * t
if b11 >= K: b11 = K
x = a11 * t
if x >= K: x = K
b11 += x
if b11 >= K: b11 = K
b12 = a11 * t
if b12 >= K: b12 = K
x = a12 * t
if x >= K: x = K
b12 += x
if b12 >= K: b12 = K
b20 = a20 * t
if b20 >= K: b20 = K
x = a22 * t
if x >= K: x = K
b20 += x
if b20 >= K: b20 = K
b21 = a20 * t
if b21 >= K: b21 = K
x = a21 * t
if x >= K: x = K
b21 += x
if b21 >= K: b21 = K
b22 = a21 * t
if b22 >= K: b22 = K
x = a22 * t
if x >= K: x = K
b22 += x
if b22 >= K: b22 = K
lv = dfs(lcl[u], b00, b01, b02, b10, b11, b12, b20, b21, b22)
if not ok:
return -1
# 左の値 lv を固定したときの変換
# lv=0(P): [0 1 0; 0 0 0; 1 0 0]
# lv=1(R): [0 0 0; 0 0 1; 0 1 0]
# lv=2(S): [1 0 1; 0 0 0; 0 0 0] ではなく makeMatFromVec([0,0,1])等の定義に従う
# 実際には:
# vec[lv]=1 のとき
# c行の c列 = vec[lose(c)]
# c行の lose(c)列 = vec[c]
if lv == 0:
# M =
# [0 1 0]
# [0 0 0]
# [1 0 0]
b00 = a02
b01 = a00
b02 = 0
b10 = a12
b11 = a10
b12 = 0
b20 = a22
b21 = a20
b22 = 0
elif lv == 1:
# M =
# [0 0 0]
# [0 0 1]
# [0 1 0]
b00 = 0
b01 = a02
b02 = a01
b10 = 0
b11 = a12
b12 = a11
b20 = 0
b21 = a22
b22 = a21
else:
# lv == 2
# M =
# [1 0 0]
# [0 0 0]
# [0 0 1]
b00 = a00
b01 = 0
b02 = a02
b10 = a10
b11 = 0
b12 = a12
b20 = a20
b21 = 0
b22 = a22
rv = dfs(rcl[u], b00, b01, b02, b10, b11, b12, b20, b21, b22)
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:
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)