結果
問題 | No.873 バイナリ、ヤバいなり!w |
ユーザー | tktk_snsn |
提出日時 | 2021-02-07 21:34:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 907 ms / 2,000 ms |
コード長 | 1,209 bytes |
コンパイル時間 | 272 ms |
コンパイル使用メモリ | 87,336 KB |
実行使用メモリ | 82,960 KB |
最終ジャッジ日時 | 2023-08-25 01:56:37 |
合計ジャッジ時間 | 36,985 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 880 ms
82,780 KB |
testcase_01 | AC | 877 ms
82,424 KB |
testcase_02 | AC | 879 ms
82,456 KB |
testcase_03 | AC | 879 ms
82,728 KB |
testcase_04 | AC | 877 ms
82,668 KB |
testcase_05 | AC | 891 ms
82,776 KB |
testcase_06 | AC | 905 ms
82,420 KB |
testcase_07 | AC | 887 ms
82,884 KB |
testcase_08 | AC | 890 ms
82,548 KB |
testcase_09 | AC | 881 ms
82,712 KB |
testcase_10 | AC | 865 ms
82,652 KB |
testcase_11 | AC | 881 ms
82,424 KB |
testcase_12 | AC | 876 ms
82,560 KB |
testcase_13 | AC | 887 ms
82,812 KB |
testcase_14 | AC | 891 ms
82,660 KB |
testcase_15 | AC | 870 ms
82,664 KB |
testcase_16 | AC | 874 ms
82,780 KB |
testcase_17 | AC | 882 ms
82,632 KB |
testcase_18 | AC | 884 ms
82,656 KB |
testcase_19 | AC | 890 ms
82,960 KB |
testcase_20 | AC | 879 ms
82,448 KB |
testcase_21 | AC | 879 ms
82,840 KB |
testcase_22 | AC | 894 ms
82,656 KB |
testcase_23 | AC | 878 ms
82,420 KB |
testcase_24 | AC | 874 ms
82,548 KB |
testcase_25 | AC | 891 ms
82,660 KB |
testcase_26 | AC | 878 ms
82,652 KB |
testcase_27 | AC | 866 ms
82,808 KB |
testcase_28 | AC | 881 ms
82,432 KB |
testcase_29 | AC | 863 ms
82,788 KB |
testcase_30 | AC | 893 ms
82,720 KB |
testcase_31 | AC | 895 ms
82,424 KB |
testcase_32 | AC | 879 ms
82,776 KB |
testcase_33 | AC | 882 ms
82,652 KB |
testcase_34 | AC | 883 ms
82,704 KB |
testcase_35 | AC | 880 ms
82,448 KB |
testcase_36 | AC | 907 ms
82,408 KB |
testcase_37 | AC | 885 ms
82,836 KB |
testcase_38 | AC | 875 ms
82,820 KB |
ソースコード
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))