結果

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

ソースコード

diff # 

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

def find_N(C_len):
    low = 1
    high = 2**16
    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 build_lookup(N):
    lookup = {}
    for num in range(1, N + 1):
        bin_str = bin(num)[2:]
        lookup[bin_str] = num
    return lookup

def build_length_map(N):
    length_map = {}
    for num in range(1, N + 1):
        l = num.bit_length()
        if l not in length_map:
            length_map[l] = []
        length_map[l].append(num)
    return length_map

def split_C(C, N, lookup, possible_lengths):
    from collections import deque
    queue = deque()
    queue.append((0, set(), []))
    while queue:
        pos, used, P = queue.popleft()
        if pos == len(C):
            if len(P) == N:
                return P
            else:
                continue
        remaining = N - len(P)
        if remaining == 0:
            continue
        for l in possible_lengths:
            end_pos = pos + l
            if end_pos > len(C):
                continue
            substr = C[pos:end_pos]
            if substr in lookup:
                num = lookup[substr]
                if num not in used:
                    new_used = used.copy()
                    new_used.add(num)
                    new_P = P.copy()
                    new_P.append(num)
                    queue.append((end_pos, new_used, new_P))
    return None

def main():
    C = input().strip()
    C_len = len(C)
    N = find_N(C_len)
    if N == -1:
        print("No solution exists")
        return
    lookup = build_lookup(N)
    possible_lengths = set()
    for num in range(1, N + 1):
        possible_lengths.add(num.bit_length())
    P = split_C(C, N, lookup, possible_lengths)
    if P:
        print(' '.join(map(str, P)))
    else:
        print("No solution found")

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