結果

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

ソースコード

diff # 

import sys
from sys import stdin

def compute_S(n):
    s = 0
    m = 1
    while (1 << (m-1)) <= n:
        lower = 1 << (m-1)
        upper = (1 << m) - 1
        if upper > n:
            upper = n
        count = upper - lower + 1
        s += count * m
        m += 1
    return s

def find_N(c_len):
    low = 1
    high = 2**20  # Arbitrary large number
    while low <= high:
        mid = (low + high) // 2
        s = compute_S(mid)
        if s == c_len:
            return mid
        elif s < c_len:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def main():
    C = stdin.read().strip()
    c_len = len(C)
    N = find_N(c_len)
    if N == -1:
        print("No solution found")
        return

    bin_numbers = {}
    for num in range(1, N+1):
        bin_str = bin(num)[2:]
        bin_numbers[bin_str] = num

    starts = [i for i, ch in enumerate(C) if ch == '1']

    used = set()
    permutation = []
    current_position = 0

    def backtrack(pos, current_used, path):
        if pos == len(C):
            if len(current_used) == N:
                return path.copy()
            else:
                return None
        if pos > len(C):
            return None
        if pos not in starts:
            return None
        for l in range(1, 17):  # since max bit is 16
            if pos + l > len(C):
                break
            substring = C[pos:pos+l]
            if substring in bin_numbers:
                num = bin_numbers[substring]
                if num not in current_used:
                    new_used = current_used.copy()
                    new_used.add(num)
                    result = backtrack(pos + l, new_used, path + [num])
                    if result is not None:
                        return result
        return None

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

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