結果

問題 No.1743 Permutation Code
ユーザー qwewe
提出日時 2025-05-14 13:23:10
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 5,834 bytes
コンパイル時間 257 ms
コンパイル使用メモリ 82,952 KB
実行使用メモリ 848,936 KB
最終ジャッジ日時 2025-05-14 13:25:16
合計ジャッジ時間 6,593 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    C = sys.stdin.readline().strip()
    n_c = len(C)

    if n_c == 0:
        sys.stdout.write("\n")
        return

    # 1. Determine N and precompute binary string lengths
    num_lengths_map = {} 
    current_sum_len = 0
    N_determined = 0
    val = 1
    while True:
        # For val > 0, val.bit_length() is len(bin(val)[2:])
        l_val = val.bit_length()
        
        num_lengths_map[val] = l_val
        current_sum_len += l_val
        
        if current_sum_len == n_c:
            N_determined = val
            break
        # According to problem statement, a solution exists, so sum will eventually match |C|.
        # Thus, current_sum_len > n_c before matching implies an invalid C or misinterpretation.
        # We assume valid inputs will lead to current_sum_len == n_c.
        val += 1
    
    # Adjust recursion limit if N_determined is large.
    # Add a buffer (e.g., N_determined + 1000). Python's default is often 1000 or 3000.
    # Max N is ~65535.
    new_recursion_limit = N_determined + 1000 
    current_limit = sys.getrecursionlimit()
    if new_recursion_limit > current_limit:
        try:
            sys.setrecursionlimit(new_recursion_limit)
        except (RecursionError, OSError): 
            # If OS limit is lower / setting fails, this might still fail for large N.
            # This is a known limitation of deep recursion in Python.
            pass

    memo_bt = {}
    NO_SOLUTION_MARKER = object() # Unique marker for "no solution found from this state"

    def backtrack_recursive(c_idx, used_numbers_fset):
        count_placed_numbers = len(used_numbers_fset)
        state = (c_idx, used_numbers_fset)

        if state in memo_bt:
            return memo_bt[state]

        if count_placed_numbers == N_determined:
            if c_idx == n_c:
                return [] # Base case: success, empty list for suffix structure
            else: # N numbers placed, but C string not fully consumed
                memo_bt[state] = NO_SOLUTION_MARKER
                return NO_SOLUTION_MARKER

        if c_idx == n_c: # Consumed C, but not N numbers placed
            memo_bt[state] = NO_SOLUTION_MARKER
            return NO_SOLUTION_MARKER
        
        if C[c_idx] == '0': # S_i must start with '1'
            memo_bt[state] = NO_SOLUTION_MARKER
            return NO_SOLUTION_MARKER

        remaining_numbers_to_place = N_determined - count_placed_numbers
        remaining_c_len = n_c - c_idx
        
        # Pruning: min length needed for remaining numbers
        min_len_needed = remaining_numbers_to_place # Each S_i has length at least 1
        if remaining_c_len < min_len_needed:
            memo_bt[state] = NO_SOLUTION_MARKER
            return NO_SOLUTION_MARKER

        # Max length of a binary string for any number up to N_determined
        # This is length of bin(N_determined)[2:]
        max_len_s_for_any_num_in_N = num_lengths_map[N_determined] 
        
        # Pruning: max length possible for remaining numbers
        max_len_possible = remaining_numbers_to_place * max_len_s_for_any_num_in_N
        if remaining_c_len > max_len_possible:
            memo_bt[state] = NO_SOLUTION_MARKER
            return NO_SOLUTION_MARKER
        
        # Iterate over possible lengths for the current S_i
        # Max length of current S_i is max_len_s_for_any_num_in_N.
        # It also cannot exceed remaining_c_len.
        # range(1, limit_val + 1) iterates from 1 to limit_val.
        max_possible_len_this_s_i = min(max_len_s_for_any_num_in_N, remaining_c_len)

        for length in range(1, max_possible_len_this_s_i + 1):
            s_i_str = C[c_idx : c_idx + length]
            # s_i_str[0] is C[c_idx], which we've confirmed is '1'.
            
            num = int(s_i_str, 2)
            
            # Validate num:
            # 1. num must be in {1..N_determined}
            if num > N_determined: 
                continue 
            
            # 2. Canonical length of bin(num) must match `length` of s_i_str.
            #    If s_i_str[0]=='1', num > 0, then num_lengths_map[num] (which is num.bit_length())
            #    will indeed be `length`. This check is technically redundant here but harmless.
            if num_lengths_map[num] != length: 
                 continue

            # 3. num must not have been used already
            if num not in used_numbers_fset:
                # Recursively call for the rest of the string and numbers
                res_suffix_markers = backtrack_recursive(c_idx + length, used_numbers_fset.union({num}))
                
                if res_suffix_markers is not NO_SOLUTION_MARKER:
                    # Solution found for suffix. Store current num and suffix structure.
                    memo_bt[state] = (num, res_suffix_markers) 
                    return (num, res_suffix_markers) 
        
        # No length choice led to a solution from this state
        memo_bt[state] = NO_SOLUTION_MARKER
        return NO_SOLUTION_MARKER

    # Initial call to the recursive solver
    solution_structure = backtrack_recursive(0, frozenset())

    if solution_structure is NO_SOLUTION_MARKER:
        # This should not be reached if a solution always exists as per problem statement.
        # For robustness in a contest, one might print an error or default.
        return

    # Reconstruct the path from the nested tuple structure
    result_permutation_str = []
    current_struct = solution_structure
    while current_struct: # An empty list [] terminates the valid structure
        num = current_struct[0]
        result_permutation_str.append(str(num))
        current_struct = current_struct[1] # Move to the rest of the structure
        
    sys.stdout.write(" ".join(result_permutation_str) + "\n")

solve()
0