結果

問題 No.1743 Permutation Code
ユーザー gew1fw
提出日時 2025-06-12 21:37:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,529 bytes
コンパイル時間 189 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 85,676 KB
最終ジャッジ日時 2025-06-12 21:41:01
合計ジャッジ時間 18,050 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

    def sum_bits(n):
        s = 0
        m = 0
        while (1 << m) <= n:
            start = 1 << m
            end = min((1 << (m + 1)) - 1, n)
            count = end - start + 1
            s += count * (m + 1)
            m += 1
        return s

    low = 1
    high = 1 << 20  # A sufficiently large upper bound
    N = -1
    while low <= high:
        mid = (low + high) // 2
        sb = sum_bits(mid)
        if sb == L:
            N = mid
            break
        elif sb < L:
            low = mid + 1
        else:
            high = mid - 1

    if N == -1:
        print("Not found")
        return

    bin_strings = {}
    for x in range(1, N + 1):
        bs = bin(x)[2:]
        bin_strings[bs] = x

    used = [False] * (N + 1)
    result = []

    def backtrack(pos):
        if pos == L:
            return True
        for x in range(1, N + 1):
            if not used[x]:
                bs = bin(x)[2:]
                l = len(bs)
                if pos + l > L:
                    continue
                if C[pos:pos + l] == bs:
                    used[x] = True
                    result.append(x)
                    if backtrack(pos + l):
                        return True
                    result.pop()
                    used[x] = False
        return False

    if backtrack(0):
        print(' '.join(map(str, result)))
    else:
        print("No solution found")

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