結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 Shiny
|
| 提出日時 | 2026-04-18 00:50:46 |
| 言語 | Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,599 bytes |
| 記録 | |
| コンパイル時間 | 629 ms |
| コンパイル使用メモリ | 20,824 KB |
| 実行使用メモリ | 61,480 KB |
| 最終ジャッジ日時 | 2026-04-18 00:51:59 |
| 合計ジャッジ時間 | 18,739 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | AC * 5 TLE * 4 -- * 19 |
ソースコード
import sys
LIMIT = 10 ** 18 + 1
CH_P = 80
CH_R = 82
CH_S = 83
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
fw = Fenwick(n)
alive = list(range(n))
for i in range(n):
fw.add(i, 1)
node = n
for pos in a:
x = fw.kth(pos)
y = fw.kth(pos + 1)
left[node] = alive[x]
right[node] = alive[y]
alive[x] = node
fw.add(y, -1)
node += 1
root = size - 1
# 0=R, 1=P, 2=S
cnt_r = [1] * size
cnt_p = [1] * size
cnt_s = [1] * size
lim = LIMIT
for v in range(n, size):
l = left[v]
r = right[v]
x0 = cnt_r[l] * cnt_s[r] + cnt_s[l] * cnt_r[r]
x1 = cnt_p[l] * cnt_r[r] + cnt_r[l] * cnt_p[r]
x2 = cnt_s[l] * cnt_p[r] + cnt_p[l] * cnt_s[r]
cnt_r[v] = lim if x0 > lim else x0
cnt_p[v] = lim if x1 > lim else x1
cnt_s[v] = lim if x2 > lim else x2
ok_r = cnt_r[root] >= k
ok_p = cnt_p[root] >= k
ok_s = cnt_s[root] >= k
if not (ok_r or ok_p or ok_s):
return ["-1", "-1", "-1"]
ans_r = bytearray(n) if ok_r else None
ans_p = bytearray(n) if ok_p else None
ans_s = bytearray(n) if ok_s else None
last_color = [-1, -1, -1]
last_k = [0, 0, 0]
mask = (ok_r << 0) | (ok_p << 1) | (ok_s << 2)
# frame:
# (v, stage, mask,
# k0, k1, k2,
# w00, w01, w02,
# w10, w11, w12,
# w20, w21, w22,
# extra0, extra1, extra2)
stack = [(root, 0, mask,
k, k, k,
1, 0, 0,
0, 1, 0,
0, 0, 1,
-1, -1, -1)]
while stack:
(v, stage, mask,
k0, k1, k2,
w00, w01, w02,
w10, w11, w12,
w20, w21, w22,
e0, e1, e2) = stack.pop()
if stage == 0:
if v < n:
if mask & 1:
rem = k0
if rem <= w01:
ans_r[v] = CH_P
last_color[0] = 1
last_k[0] = rem
else:
rem -= w01
if rem <= w00:
ans_r[v] = CH_R
last_color[0] = 0
last_k[0] = rem
else:
ans_r[v] = CH_S
last_color[0] = 2
last_k[0] = rem - w00
if mask & 2:
rem = k1
if rem <= w11:
ans_p[v] = CH_P
last_color[1] = 1
last_k[1] = rem
else:
rem -= w11
if rem <= w10:
ans_p[v] = CH_R
last_color[1] = 0
last_k[1] = rem
else:
ans_p[v] = CH_S
last_color[1] = 2
last_k[1] = rem - w10
if mask & 4:
rem = k2
if rem <= w21:
ans_s[v] = CH_P
last_color[2] = 1
last_k[2] = rem
else:
rem -= w21
if rem <= w20:
ans_s[v] = CH_R
last_color[2] = 0
last_k[2] = rem
else:
ans_s[v] = CH_S
last_color[2] = 2
last_k[2] = rem - w20
continue
l = left[v]
r = right[v]
rc0 = cnt_r[r]
rc1 = cnt_p[r]
rc2 = cnt_s[r]
if mask & 1:
lw00 = rc2 * w00 + rc1 * w01
lw01 = rc0 * w01 + rc2 * w02
lw02 = rc1 * w02 + rc0 * w00
if lw00 > lim:
lw00 = lim
if lw01 > lim:
lw01 = lim
if lw02 > lim:
lw02 = lim
else:
lw00 = lw01 = lw02 = 0
if mask & 2:
lw10 = rc2 * w10 + rc1 * w11
lw11 = rc0 * w11 + rc2 * w12
lw12 = rc1 * w12 + rc0 * w10
if lw10 > lim:
lw10 = lim
if lw11 > lim:
lw11 = lim
if lw12 > lim:
lw12 = lim
else:
lw10 = lw11 = lw12 = 0
if mask & 4:
lw20 = rc2 * w20 + rc1 * w21
lw21 = rc0 * w21 + rc2 * w22
lw22 = rc1 * w22 + rc0 * w20
if lw20 > lim:
lw20 = lim
if lw21 > lim:
lw21 = lim
if lw22 > lim:
lw22 = lim
else:
lw20 = lw21 = lw22 = 0
stack.append((v, 1, mask,
k0, k1, k2,
w00, w01, w02,
w10, w11, w12,
w20, w21, w22,
-1, -1, -1))
stack.append((l, 0, mask,
k0, k1, k2,
lw00, lw01, lw02,
lw10, lw11, lw12,
lw20, lw21, lw22,
-1, -1, -1))
elif stage == 1:
ne0 = last_color[0] if (mask & 1) else -1
ne1 = last_color[1] if (mask & 2) else -1
ne2 = last_color[2] if (mask & 4) else -1
nk0 = last_k[0] if (mask & 1) else 0
nk1 = last_k[1] if (mask & 2) else 0
nk2 = last_k[2] if (mask & 4) else 0
if mask & 1:
lc = ne0
if lc == 0:
rw00, rw01, rw02 = 0, w01, w00
elif lc == 1:
rw00, rw01, rw02 = w01, 0, w02
else:
rw00, rw01, rw02 = w00, w02, 0
else:
rw00 = rw01 = rw02 = 0
if mask & 2:
lc = ne1
if lc == 0:
rw10, rw11, rw12 = 0, w11, w10
elif lc == 1:
rw10, rw11, rw12 = w11, 0, w12
else:
rw10, rw11, rw12 = w10, w12, 0
else:
rw10 = rw11 = rw12 = 0
if mask & 4:
lc = ne2
if lc == 0:
rw20, rw21, rw22 = 0, w21, w20
elif lc == 1:
rw20, rw21, rw22 = w21, 0, w22
else:
rw20, rw21, rw22 = w20, w22, 0
else:
rw20 = rw21 = rw22 = 0
stack.append((v, 2, mask,
nk0, nk1, nk2,
w00, w01, w02,
w10, w11, w12,
w20, w21, w22,
ne0, ne1, ne2))
r = right[v]
stack.append((r, 0, mask,
nk0, nk1, nk2,
rw00, rw01, rw02,
rw10, rw11, rw12,
rw20, rw21, rw22,
-1, -1, -1))
else:
if mask & 1:
lc = e0
rc = last_color[0]
if lc == 0:
last_color[0] = 0 if rc == 2 else 1
elif lc == 1:
last_color[0] = 1 if rc == 0 else 2
else:
last_color[0] = 2 if rc == 1 else 0
if mask & 2:
lc = e1
rc = last_color[1]
if lc == 0:
last_color[1] = 0 if rc == 2 else 1
elif lc == 1:
last_color[1] = 1 if rc == 0 else 2
else:
last_color[1] = 2 if rc == 1 else 0
if mask & 4:
lc = e2
rc = last_color[2]
if lc == 0:
last_color[2] = 0 if rc == 2 else 1
elif lc == 1:
last_color[2] = 1 if rc == 0 else 2
else:
last_color[2] = 2 if rc == 1 else 0
return [
ans_r.decode() if ok_r else "-1",
ans_p.decode() if ok_p else "-1",
ans_s.decode() if ok_s else "-1",
]
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()