結果

問題 No.873 バイナリ、ヤバいなり!w
ユーザー tktk_snsn
提出日時 2021-02-07 21:34:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 831 ms / 2,000 ms
コード長 1,209 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,372 KB
実行使用メモリ 81,304 KB
最終ジャッジ日時 2024-12-23 13:55:46
合計ジャッジ時間 32,634 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import deque
U = 3 * 10 ** 5
Usq = int(U ** 0.5 + 0.5)
dp = [U] * (U + 1)
prev = [-1] * (U + 1) # p*p-1
for i in range(Usq):
prev[i*i] = i
dp[i*i] = i
od = [(1, 1)]
ev = []
for i in range(2, U + 1):
for j, s in od:
if dp[i] > dp[i - s] + j:
dp[i] = dp[i - s] + j
prev[i] = j
for j, s in ev[::-1]:
if dp[i] > dp[i - s] + j:
dp[i] = dp[i - s] + j
prev[i] = j
if dp[i] ** 2 == i:
if i % 2 == 1:
od.append((dp[i], i))
else:
ev.append((dp[i], i))
N = int(input())
seq = []
i = N
while i:
p = prev[i]
seq.append(p)
i -= p * p
seq.sort()
odd = []
even = []
for s in seq:
if s % 2 == 0:
even.append(s)
else:
odd.append(s)
ans = []
for s in odd:
bit = "".join(["0" if i % 2 == 0 else "1" for i in range(s)])
ans.append(bit)
even = deque(even)
rev = 0
while even:
if rev:
s = even.popleft()
else:
s = even.pop()
bit = "".join(["0" if i % 2 == 0 else "1" for i in range(s)])
if rev:
bit = bit[::-1]
ans.append(bit)
rev = 1 - rev
print("".join(ans))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0