結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def find_n(len_c):
    m = 1
    total_bits = 0
    while True:
        start = 2 ** (m - 1)
        end = 2 ** m - 1
        if start > len_c:
            return None  # Not possible, but per problem statement, C is valid.
        if end <= len_c:
            count = end - start + 1
        else:
            count = len_c - start + 1
        total_bits += m * count
        if total_bits == len_c:
            return end
        if total_bits > len_c:
            # Adjust to find correct N
            while True:
                end -= 1
                if end < start:
                    break
                total_bits -= m
                if total_bits == len_c:
                    return end
            while True:
                m -= 1
                start = 2 ** (m - 1)
                if start == 1:
                    break
                end = 2 ** m - 1
                count = end - start + 1
                total_bits -= m * count
                if total_bits < len_c:
                    total_bits += m
                    return end - count + 1
        m += 1

def main():
    C = sys.stdin.readline().strip()
    L = len(C)
    N = find_n(L)
    if N is None:
        print("1")  # Shouldn't happen as per problem statement
        return

    binary_map = {}
    for num in range(1, N+1):
        binary = bin(num)[2:]
        binary_map[binary] = num

    used = set()
    result = []

    def backtrack(pos):
        if pos == L:
            return True
        for binary_str, num in binary_map.items():
            if num in used:
                continue
            if C[pos:pos+len(binary_str)] == binary_str:
                used.add(num)
                result.append(num)
                if backtrack(pos + len(binary_str)):
                    return True
                used.remove(num)
                result.pop()
        return False

    if backtrack(0):
        print(' '.join(map(str, result)))
    else:
        print("1")  # Shouldn't happen as per problem statement

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