結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 Shiny
|
| 提出日時 | 2026-04-18 01:13:42 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 494 ms / 2,000 ms |
| コード長 | 5,327 bytes |
| 記録 | |
| コンパイル時間 | 467 ms |
| コンパイル使用メモリ | 85,760 KB |
| 実行使用メモリ | 215,840 KB |
| 最終ジャッジ日時 | 2026-04-18 01:14:02 |
| 合計ジャッジ時間 | 17,187 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 |
ソースコード
import sys
LIM = 10 ** 18 + 1
CP, CR, CS = 80, 82, 83
class BIT:
__slots__ = ('n', 'bit')
def __init__(self, n):
self.n = n
self.bit = [0] * (n + 1)
def add(self, i, x):
i += 1
bit = self.bit
n = self.n
while i <= n:
bit[i] += x
i += i & -i
def kth(self, k):
idx = 0
bit = self.bit
n = self.n
step = 1 << (n.bit_length() - 1)
while step:
ni = idx + step
if ni <= n and bit[ni] < k:
idx = ni
k -= bit[ni]
step >>= 1
return idx
def solve_one(n, k, a):
p2 = [1] * (n + 1)
for i in range(1, n + 1):
v = p2[i - 1] << 1
p2[i] = LIM if v > LIM else v
# 각 최종 문자 R/P/S가 되는 문자열 개수는 항상 2^(N-1)
if k > p2[n - 1]:
return ['-1', '-1', '-1']
m = 2 * n - 1
left = [0] * m
right = [0] * m
size = [1] * m
ways = [1] * m
bit = BIT(n)
cur = list(range(n))
nxt = list(range(n + 1))
for i in range(n):
bit.add(i, 1)
def find(x):
while nxt[x] != x:
nxt[x] = nxt[nxt[x]]
x = nxt[x]
return x
node = n
for x in a:
lpos = bit.kth(x)
rpos = find(lpos + 1)
l = cur[lpos]
r = cur[rpos]
left[node] = l
right[node] = r
cur[lpos] = node
bit.add(rpos, -1)
nxt[rpos] = find(rpos + 1)
s = size[l] + size[r]
size[node] = s
ways[node] = p2[s - 1]
node += 1
root = m - 1
def build(target):
ans = bytearray(n)
st_v = [root]
st_type = [0]
st_k = [k]
st_w0 = [1 if target == 0 else 0]
st_w1 = [1 if target == 1 else 0]
st_w2 = [1 if target == 2 else 0]
st_extra = [-1]
last_color = -1
last_k = 0
while st_v:
v = st_v.pop()
typ = st_type.pop()
cur_k = st_k.pop()
w0 = st_w0.pop()
w1 = st_w1.pop()
w2 = st_w2.pop()
extra = st_extra.pop()
if typ == 0:
if v < n:
rem = cur_k
# 사전순은 P < R < S
if rem <= w1:
ans[v] = CP
last_color = 1
last_k = rem
else:
rem -= w1
if rem <= w0:
ans[v] = CR
last_color = 0
last_k = rem
else:
ans[v] = CS
last_color = 2
last_k = rem - w0
continue
l = left[v]
r = right[v]
rw = ways[r]
nw0 = rw * (w0 + w1)
nw1 = rw * (w1 + w2)
nw2 = rw * (w2 + w0)
if nw0 > LIM:
nw0 = LIM
if nw1 > LIM:
nw1 = LIM
if nw2 > LIM:
nw2 = LIM
st_v.append(v)
st_type.append(1)
st_k.append(cur_k)
st_w0.append(w0)
st_w1.append(w1)
st_w2.append(w2)
st_extra.append(-1)
st_v.append(l)
st_type.append(0)
st_k.append(cur_k)
st_w0.append(nw0)
st_w1.append(nw1)
st_w2.append(nw2)
st_extra.append(-1)
elif typ == 1:
lc = last_color
rem = last_k
if lc == 0: # left = R
nw0, nw1, nw2 = 0, w1, w0
elif lc == 1: # left = P
nw0, nw1, nw2 = w1, 0, w2
else: # left = S
nw0, nw1, nw2 = w0, w2, 0
st_v.append(v)
st_type.append(2)
st_k.append(rem)
st_w0.append(w0)
st_w1.append(w1)
st_w2.append(w2)
st_extra.append(lc)
st_v.append(right[v])
st_type.append(0)
st_k.append(rem)
st_w0.append(nw0)
st_w1.append(nw1)
st_w2.append(nw2)
st_extra.append(-1)
else:
lc = extra
rc = last_color
if lc == 0:
last_color = 0 if rc == 2 else 1
elif lc == 1:
last_color = 1 if rc == 0 else 2
else:
last_color = 2 if rc == 1 else 0
return ans.decode()
return [build(0), build(1), build(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_one(n, k, a))
sys.stdout.write('\n'.join(out))
if __name__ == '__main__':
main()