結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 Naru820
|
| 提出日時 | 2026-04-01 10:34:42 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,596 bytes |
| 記録 | |
| コンパイル時間 | 568 ms |
| コンパイル使用メモリ | 85,376 KB |
| 実行使用メモリ | 442,372 KB |
| 最終ジャッジ日時 | 2026-04-17 19:59:17 |
| 合計ジャッジ時間 | 24,735 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 |
| other | WA * 25 TLE * 3 |
ソースコード
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1 << 20)
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 = []
K = k
ll = l
rr = r
ssz = sz
tp = twopow
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 ll[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 = tp[ssz[rr[u]] - 1]
# A * freeMat(t)
# freeMat =
# [t t 0]
# [0 t t]
# [t 0 t]
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(ll[u], b00, b01, b02, b10, b11, b12, b20, b21, b22)
if not ok:
return -1
# A * fixedMat(lv)
if lv == 0:
# [0 1 0]
# [0 0 0]
# [1 0 0]
b00, b01, b02 = a02, a00, 0
b10, b11, b12 = a12, a10, 0
b20, b21, b22 = a22, a20, 0
elif lv == 1:
# [0 0 0]
# [0 0 1]
# [0 1 0]
b00, b01, b02 = 0, a02, a01
b10, b11, b12 = 0, a12, a11
b20, b21, b22 = 0, a22, a21
else:
# lv == 2
# [1 0 0]
# [0 0 1]
# [0 0 0]
b00, b01, b02 = a00, 0, 0
b10, b11, b12 = a10, 0, a11
b20, b21, b22 = a20, 0, a21
rv = dfs(rr[u], b00, b01, b02, b10, b11, b12, b20, b21, b22)
if not ok:
return -1
if lv == rv:
return -1
if (lv == 0 and rv == 1) or (lv == 1 and rv == 2) or (lv == 2 and rv == 0):
return lv
return rv
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)