結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    C = sys.stdin.readline().strip()
    L = len(C)
    
    # Function to compute the sum of binary lengths for numbers 1 to N
    def compute_S(N):
        s = 0
        m = 1
        while m <= N:
            next_m = m * 2
            if next_m > N:
                next_m = N + 1
            count = next_m - m
            bits = m.bit_length()
            s += count * bits
            m = next_m
        return s
    
    # Find N such that compute_S(N) == L
    low = 1
    high = 1
    while compute_S(high) < L:
        high *= 2
    
    N = high
    while low <= high:
        mid = (low + high) // 2
        s = compute_S(mid)
        if s == L:
            N = mid
            break
        elif s < L:
            low = mid + 1
        else:
            high = mid - 1
    
    # Precompute binary representations
    binary = {}
    for num in range(1, N+1):
        binary[num] = bin(num)[2:]
    
    # Precompute lengths
    len_dict = defaultdict(list)
    for num in binary:
        l = len(binary[num])
        len_dict[l].append(num)
    
    # Now, try to split C into the binary representations
    # Using recursive backtracking with memoization
    
    memo = {}
    result = None
    
    def backtrack(pos, used, path):
        nonlocal result
        if result is not None:
            return
        if pos == len(C):
            if len(used) == N:
                result = path.copy()
            return
        if pos in memo:
            return
        memo[pos] = True
        remaining = len(C) - pos
        max_len = min(remaining, 17)
        for l in range(1, max_len+1):
            if pos + l > len(C):
                continue
            s = C[pos:pos+l]
            if s in binary.values():
                # Find the number(s) that match this binary string
                for num in binary:
                    if binary[num] == s and num not in used:
                        used.add(num)
                        path.append(num)
                        backtrack(pos + l, used, path)
                        if result is not None:
                            return
                        used.remove(num)
                        path.pop()
        del memo[pos]
    
    used = set()
    path = []
    backtrack(0, used, path)
    
    print(' '.join(map(str, result)))

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