結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
from collections import dequeU = 3 * 10 ** 5Usq = 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] = idp[i*i] = iod = [(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] + jprev[i] = jfor j, s in ev[::-1]:if dp[i] > dp[i - s] + j:dp[i] = dp[i - s] + jprev[i] = jif dp[i] ** 2 == i:if i % 2 == 1:od.append((dp[i], i))else:ev.append((dp[i], i))N = int(input())seq = []i = Nwhile i:p = prev[i]seq.append(p)i -= p * pseq.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 = 0while 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 - revprint("".join(ans))