結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー |
|
提出日時 | 2023-07-21 21:56:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 576 ms / 2,000 ms |
コード長 | 1,081 bytes |
コンパイル時間 | 249 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 64,512 KB |
最終ジャッジ日時 | 2024-09-21 23:28:18 |
合計ジャッジ時間 | 7,280 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
from collections import dequeINF = 2 ** 60def get_priority(length):if length % 2 == 1:return lengthelse:return INF - lengthn = int(input())dp = [INF] * (n+1)dp[0] = 0for i in range(1, n+1):j = 1while True:val = j * jif val > i:breakdp[i] = min(dp[i], dp[i-val]+j)j += 1use_lengths = []target = nwhile target > 0:cands = []for i in range(1, n+1):val = i * iif val > target:breakif dp[target-val]+i == dp[target]:cands.append(i)cands.sort(key=lambda v: get_priority(v))use_lengths.append(cands[0])target -= cands[0] * cands[0]use_lengths.sort(key=lambda v: get_priority(v))odds = [v for v in use_lengths if v % 2 == 1]evens = deque([v for v in use_lengths if v % 2 == 0])result = ""for v in odds:result += "0" + "10" * (v//2)limit = len(evens)for i in range(limit):if i % 2 == 0:result += "01" * (evens.popleft()//2)else:result += "10" * (evens.pop()//2)print(result)