結果

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

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    C = sys.stdin.readline().strip()
    L = len(C)
    
    # Function to compute sum of bits for numbers 1..N
    def sum_bits(N):
        total = 0
        m = 1
        while (1 << (m-1)) <= N:
            start = 1 << (m-1)
            end = (1 << m) - 1
            if end > N:
                end = N
            count = end - start + 1
            total += count * m
            m += 1
        return total
    
    # Binary search to find N
    low = 1
    high = 2 * 10**6  # Arbitrary large value
    found = None
    while low <= high:
        mid = (low + high) // 2
        s = sum_bits(mid)
        if s == L:
            found = mid
            break
        elif s < L:
            low = mid + 1
        else:
            high = mid - 1
    if not found:
        print("No solution found")
        return
    
    N = found
    print("N =", N, file=sys.stderr)
    
    # Precompute binary strings and their integer values
    binary_dict = {}
    for i in range(1, N+1):
        binary = bin(i)[2:]
        binary_dict[binary] = i
    
    # Precompute all possible binary strings and their end positions
    binary_strings = list(binary_dict.keys())
    max_len = max(len(s) for s in binary_strings)
    
    # Backtracking with memoization
    permutation = []
    used = [False] * (N + 1)
    result = None
    
    def backtrack(pos):
        nonlocal result
        if result is not None:
            return
        if pos == len(C):
            if len(permutation) == N:
                result = permutation.copy()
            return
        if pos > len(C):
            return
        # Try all possible binary strings starting at pos
        for m in range(1, max_len + 1):
            if pos + m > len(C):
                continue
            substring = C[pos:pos+m]
            if substring in binary_dict:
                num = binary_dict[substring]
                if not used[num]:
                    used[num] = True
                    permutation.append(num)
                    backtrack(pos + m)
                    if result is not None:
                        return
                    permutation.pop()
                    used[num] = False
    
    backtrack(0)
    
    if result is None:
        print("No solution found")
    else:
        print(' '.join(map(str, result)))
    
if __name__ == "__main__":
    main()
0