結果

問題 No.1743 Permutation Code
ユーザー gew1fw
提出日時 2025-06-12 16:43:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,987 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 99,444 KB
最終ジャッジ日時 2025-06-12 16:44:15
合計ジャッジ時間 12,655 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 2 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    C = sys.stdin.readline().strip()
    len_C = len(C)
    if len_C == 0:
        print()
        return

    # Compute N such that sum_{k=1 to N} (bits of k) = len_C
    N = 0
    total_bits = 0
    while True:
        N += 1
        bits = N.bit_length()
        total_bits += bits
        if total_bits == len_C:
            break
        elif total_bits > len_C:
            N -= 1
            total_bits -= (N.bit_length())
            break

    # Precompute the maximum possible binary length for N
    max_bits = N.bit_length()

    # Collect positions of '1's
    ones_pos = [i for i, c in enumerate(C) if c == '1']

    # For each '1' position, we'll try to read the binary number
    used = [False] * (N + 1)
    result = []
    current_pos = 0

    def backtrack(pos, used_set, path):
        if pos == len_C:
            if len(path) == N:
                print(' '.join(map(str, path)))
                return True
            return False
        if pos > len_C:
            return False
        # Find the next '1' starting from pos
        for i in range(len(ones_pos)):
            if ones_pos[i] >= pos:
                start = ones_pos[i]
                break
        else:
            return False
        # Try all possible lengths from 1 to max_bits
        for l in range(1, max_bits + 1):
            end = start + l
            if end > len_C:
                continue
            binary = C[start:end]
            num = int(binary, 2)
            if num < 1 or num > N:
                continue
            if not used_set[num]:
                used_set[num] = True
                path.append(num)
                if backtrack(end, used_set, path):
                    return True
                path.pop()
                used_set[num] = False
        return False

    used = [False] * (N + 1)
    if backtrack(0, used, []):
        pass
    else:
        pass

if __name__ == '__main__':
    main()
0