結果

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

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    C = sys.stdin.read().strip()
    L = len(C)
    
    # Step 1: Compute N
    sum_bits = 0
    N = 0
    while True:
        N += 1
        bits = N.bit_length()
        sum_bits += bits
        if sum_bits == L:
            break
        elif sum_bits > L:
            print("No solution found", file=sys.stderr)
            return
    
    # Step 2: Precompute all binary strings for 1..N
    binary_strings = [bin(x)[2:] for x in range(1, N+1)]
    binary_dict = {s: x for x, s in enumerate(binary_strings, 1)}
    max_len = max(len(s) for s in binary_strings)
    
    # Step 3: Backtracking approach
    result = []
    used = set()
    
    def backtrack(pos, used_set, permutation):
        nonlocal result
        if pos == len(C):
            if len(used_set) == N:
                result = permutation.copy()
            return
        if result:
            return
        # Try all possible lengths from max_len down to 1
        for l in range(max_len, 0, -1):
            if pos + l > len(C):
                continue
            substr = C[pos:pos+l]
            if substr in binary_dict:
                x = binary_dict[substr]
                if x not in used_set:
                    new_used = used_set.copy()
                    new_used.add(x)
                    backtrack(pos + l, new_used, permutation + [x])
            if result:
                return
    
    backtrack(0, set(), [])
    print(' '.join(map(str, result)))
    
if __name__ == "__main__":
    main()
0