結果

問題 No.1743 Permutation Code
ユーザー gew1fw
提出日時 2025-06-12 16:49:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,613 bytes
コンパイル時間 241 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 86,780 KB
最終ジャッジ日時 2025-06-12 16:50:21
合計ジャッジ時間 10,770 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    C = sys.stdin.readline().strip()
    L = len(C)

    # 预计算k的可能值
    def compute_sum(k):
        return sum(len(bin(i)) - 2 for i in range(1, k + 1))

    # 使用二分查找找到k的可能值
    low = 1
    high = 1
    while compute_sum(high) < L:
        high *= 2

    k = None
    left = 1
    right = high
    while left <= right:
        mid = (left + right) // 2
        s = compute_sum(mid)
        if s == L:
            k = mid
            break
        elif s < L:
            left = mid + 1
        else:
            right = mid - 1
    if k is None:
        # 根据题目描述，一定存在解，所以这个情况理论上不会发生
        return

    # 预处理二进制字符串
    binary = {}
    for d in range(1, k + 1):
        binary[d] = bin(d)[2:]

    # 回溯函数
    used = set()
    path = []
    result = None

    def backtrack(pos):
        nonlocal result
        if pos == len(C):
            if len(path) == k and len(used) == k:
                result = list(path)
            return
        for d in range(k, 0, -1):
            if d in used:
                continue
            s = binary[d]
            l = len(s)
            if pos + l > len(C):
                continue
            if C[pos:pos + l] != s:
                continue
            used.add(d)
            path.append(d)
            backtrack(pos + l)
            if result is not None:
                return
            used.remove(d)
            path.pop()

    backtrack(0)
    print(' '.join(map(str, result)))

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