結果

問題 No.873 バイナリ、ヤバいなり！ｗ
ユーザー gew1fw
提出日時 2025-06-12 21:43:08
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,907 bytes
コンパイル時間 409 ms
コンパイル使用メモリ 82,328 KB
実行使用メモリ 85,496 KB
最終ジャッジ日時 2025-06-12 21:47:10
合計ジャッジ時間 6,252 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def find_decomposition(N):
    if N == 0:
        return []
    dp = [float('inf')] * (N + 1)
    dp[0] = 0
    parent = [None] * (N + 1)
    for i in range(1, N + 1):
        max_j = int(math.isqrt(i))
        for j in range(1, max_j + 1):
            if dp[i - j*j] + j < dp[i]:
                dp[i] = dp[i - j*j] + j
                parent[i] = j
    # Reconstruct the decomposition
    a = []
    current = N
    while current > 0:
        j = parent[current]
        a.append(j)
        current -= j * j
    return a

def generate_binary_string(a):
    a_sorted = sorted(a)
    # Split into 0-starting and 1-starting groups
    zero_group = []
    one_group = []
    for i in range(len(a_sorted)):
        if i % 2 == 0:
            zero_group.append(a_sorted[i])
        else:
            one_group.append(a_sorted[i])
    zero_group.sort()
    one_group.sort()
    # Reconstruct the a list for interleaving
    final_a = []
    z_ptr = 0
    o_ptr = 0
    for i in range(len(a_sorted)):
        if i % 2 == 0:
            if z_ptr < len(zero_group):
                final_a.append(zero_group[z_ptr])
                z_ptr += 1
        else:
            if o_ptr < len(one_group):
                final_a.append(one_group[o_ptr])
                o_ptr += 1
    # Now build the binary string
    binary = []
    current_char = '0'
    for ai in final_a:
        part = []
        for _ in range(ai):
            part.append(current_char)
            current_char = '1' if current_char == '0' else '0'
        binary.append(''.join(part))
        # Toggle current_char for the next part
        current_char = '1' if current_char == '0' else '0'
    return ''.join(binary)

# Read input
N = int(input())
# Handle N=0 case
if N == 0:
    print("")
else:
    a = find_decomposition(N)
    if not a:
        print("")
    else:
        binary = generate_binary_string(a)
        print(binary)
0