結果

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

ソースコード

diff # 

import sys
from collections import defaultdict

def compute_S(n):
    s = 0
    for i in range(1, n+1):
        s += (i).bit_length()
    return s

def find_n(c_length):
    low = 1
    high = 10**6  # Arbitrary large number
    while low <= high:
        mid = (low + high) // 2
        s = compute_S(mid)
        if s == c_length:
            return mid
        elif s < c_length:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # Not found

def main():
    C = sys.stdin.read().strip()
    c_length = len(C)
    N = find_n(c_length)
    if N == -1:
        print("Invalid input")
        return

    max_bits = (N).bit_length()
    expected_counts = defaultdict(int)
    for l in range(1, max_bits + 1):
        start = 2**(l-1)
        end = 2**l - 1
        if start > N:
            break
        count = min(end, N) - start + 1
        expected_counts[l] = count

    current = 0
    used = set()
    result = []
    len_C = len(C)

    from itertools import permutations
    from bisect import bisect_left

    def backtrack(pos, used, path):
        if pos == len_C:
            if len(path) == N:
                print(' '.join(map(str, path)))
                return True
            return False
        for l in range(1, max_bits + 1):
            if pos + l > len_C:
                continue
            binary = C[pos:pos+l]
            if binary[0] == '0':
                continue  # Leading zero not allowed
            num = int(binary, 2)
            if 1 <= num <= N and num not in used:
                used.add(num)
                if backtrack(pos + l, used, path + [num]):
                    return True
                used.remove(num)
        return False

    if backtrack(0, set(), []):
        return
    print("No solution found")

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