結果

問題 No.1743 Permutation Code
ユーザー gew1fw
提出日時 2025-06-12 20:22:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,192 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 81,708 KB
実行使用メモリ 194,592 KB
最終ジャッジ日時 2025-06-12 20:23:07
合計ジャッジ時間 12,108 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    C = sys.stdin.readline().strip()
    L = len(C)
    if L == 0:
        print()
        return
    
    # Step 1: Compute N such that sum of bit lengths from 1..N is L
    def get_bit_length(x):
        return x.bit_length()
    
    sum_bit = 0
    N = 0
    while sum_bit < L:
        N += 1
        sum_bit += get_bit_length(N)
    if sum_bit != L:
        print("Invalid C")
        return
    
    # Step 2: Precompute bit lengths and counts
    bit_counts = {}
    for num in range(1, N+1):
        bl = get_bit_length(num)
        if bl in bit_counts:
            bit_counts[bl] += 1
        else:
            bit_counts[bl] = 1
    
    # Precompute binary strings for quick lookup
    binary_dict = {}
    for num in range(1, N+1):
        binary_dict[num] = bin(num)[2:]
    
    # Step 3: Recursive backtracking with memoization
    from functools import lru_cache
    
    current_pos = 0
    used = set()
    counts = bit_counts.copy()
    result = []
    
    # We'll use a helper function to perform backtracking
    def backtrack(pos, counts_left, used_numbers, current_result):
        if pos == L:
            return current_result
        for bl in list(counts_left.keys()):
            if counts_left[bl] == 0:
                continue
            if pos + bl > L:
                continue
            substring = C[pos:pos+bl]
            if substring[0] != '1':
                continue
            num = int(substring, 2)
            if num < 1 or num > N or num in used_numbers:
                continue
            new_counts = counts_left.copy()
            new_counts[bl] -= 1
            new_used = used_numbers.copy()
            new_used.add(num)
            new_result = current_result.copy()
            new_result.append(num)
            res = backtrack(pos + bl, new_counts, new_used, new_result)
            if res is not None:
                return res
        return None
    
    permutation = backtrack(0, counts, set(), [])
    if permutation is None:
        print("No solution found")
    else:
        print(' '.join(map(str, permutation)))
    
if __name__ == "__main__":
    main()
0