結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
![]() |
提出日時 | 2023-10-19 21:21:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,106 ms / 2,000 ms |
コード長 | 1,469 bytes |
コンパイル時間 | 198 ms |
コンパイル使用メモリ | 82,444 KB |
実行使用メモリ | 78,368 KB |
最終ジャッジ日時 | 2024-09-19 17:24:06 |
合計ジャッジ時間 | 10,539 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
from collections import *def main():N = int(input())M = int(N ** 0.5) + 2inf = 10 ** 18dp = [inf] * (N + 1)dp[0] = 0for i in range(N):for j in range(1, M + 1):nex = i + j * jif i + j * j > N:breakdp[nex] = min(dp[nex], dp[i] + j)L = []now = Nfor i in range(1, M, 2):while now >= i * i:if dp[now] == dp[now - i * i] + i:now -= i * iL.append(i)continueelse:breakfor i in range(2, M, 2):while now >= i * i:if dp[now] == dp[now - i * i] + i:now -= i * iL.append(i)continueelse:breakdef f(t):odd, even = [], []for i in range(len(t)):if t[i] % 2:odd.append(t[i])else:even.append(t[i])odd.sort()even.sort()even = deque(even)cnt = 0while even:if cnt % 2:odd.append(even.popleft())else:odd.append(even.pop())cnt += 1lst = []now = 0for a in odd:for i in range(a):lst.append(str(now))now = 1 - nownow = 1 - nowreturn "".join(lst)print(f(L))main()