結果

問題 No.873 バイナリ、ヤバいなり！ｗ
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:25:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,279 bytes
コンパイル時間 438 ms
コンパイル使用メモリ 81,780 KB
実行使用メモリ 137,860 KB
最終ジャッジ日時 2025-05-14 13:27:09
合計ジャッジ時間 6,922 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Generator for characters of the string S(L_list)
def generate_chars(L_list):
    current_start_char_val = 0 # Start Q1 with '0'
    for l_val in L_list:
        if l_val == 0: # Should not happen with positive lengths
            continue
        
        char_for_segment = current_start_char_val
        for _ in range(l_val):
            yield char_for_segment # Yield 0 or 1
            char_for_segment = 1 - char_for_segment
        
        # Determine the last character of the segment just generated
        # This will be the starting character for the next segment
        # If l_val is odd, last char is same as start char. If even, it's different.
        if l_val % 2 == 1:
            current_start_char_val = current_start_char_val 
        else:
            current_start_char_val = 1 - current_start_char_val

# Compares strings S(L1) and S(L2). Returns True if S(L1) < S(L2).
def compare_lex_lists(L1, L2):
    s1_iter = generate_chars(L1)
    s2_iter = generate_chars(L2)

    while True:
        c1 = next(s1_iter, -1) # Use -1 as sentinel for end-of-string
        c2 = next(s2_iter, -1)

        if c1 == -1 and c2 == -1: # Both ended, strings are equal
            return False # L1 is not strictly smaller
        if c1 == -1: # S1 ended, S2 continues. S1 is prefix, hence smaller.
            return True
        if c2 == -1: # S2 ended, S1 continues. S2 is prefix, hence smaller.
            return False # L1 is not smaller than L2
        
        if c1 < c2:
            return True
        if c1 > c2:
            return False
        # Characters are equal, continue to next character

def solve():
    N = int(sys.stdin.readline())

    # dp_list[i] stores (min_sum_lengths, list_of_lengths L) for sum_of_squares = i
    dp_list = [None] * (N + 1)
    dp_list[0] = (0, [])

    for i in range(N): 
        if dp_list[i] is None:
            continue

        current_sum_len, current_L_list = dp_list[i]

        j = 1 # l_val for the new segment
        while True:
            next_sum_sq = i + j*j
            if next_sum_sq > N:
                break

            new_sum_len = current_sum_len + j
            # Potential new list of lengths for sum_sq = next_sum_sq

            if dp_list[next_sum_sq] is None or new_sum_len < dp_list[next_sum_sq][0]:
                # Found a path with smaller sum_len, or first path
                # Python list concatenation creates a new list, effectively copying.
                new_L_list = current_L_list + [j] 
                dp_list[next_sum_sq] = (new_sum_len, new_L_list)
            elif new_sum_len == dp_list[next_sum_sq][0]:
                # Tie in sum_len, compare lexicographically
                # Construct new_L_list only if needed for comparison
                new_L_list = current_L_list + [j]
                existing_L_list = dp_list[next_sum_sq][1]
                
                if compare_lex_lists(new_L_list, existing_L_list):
                    dp_list[next_sum_sq] = (new_sum_len, new_L_list)
            
            j += 1
            
    _, best_L_list_final = dp_list[N]
    
    ans_chars = []
    for char_val in generate_chars(best_L_list_final):
        ans_chars.append(str(char_val))

    sys.stdout.write("".join(ans_chars) + "\n")

solve()
0