結果

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

ソースコード

diff # 

C = input().strip()
L = len(C)

def sum_bit_length(N):
    s = 0
    b = 1
    while (1 << (b-1)) <= N:
        start = 1 << (b-1)
        end = (1 << b) - 1
        if end > N:
            end = N
        count = end - start + 1
        s += count * b
        b += 1
    return s

low = 1
high = L
N = 0
while low <= high:
    mid = (low + high) // 2
    s = sum_bit_length(mid)
    if s == L:
        N = mid
        break
    elif s < L:
        low = mid + 1
    else:
        high = mid - 1

from collections import defaultdict

binary_map = defaultdict(dict)
count = defaultdict(int)
for k in range(1, N + 1):
    s = bin(k)[2:]
    b = len(s)
    binary_map[b][s] = k
    count[b] += 1

def backtrack():
    # Using iterative approach with stack to avoid recursion depth issues
    stack = []
    import copy
    # Each element in the stack is a tuple (i, used_set, count_remaining, path)
    # Initialize with starting parameters
    initial_used = set()
    initial_count = copy.deepcopy(count)
    initial_path = []
    stack.append((0, initial_used, initial_count, initial_path))
    
    while stack:
        i, used, count_rem, path = stack.pop()
        if i == L:
            return path
        # Try possible bit lengths in reverse order (larger first)
        for b in sorted(binary_map.keys(), reverse=True):
            if count_rem.get(b, 0) <= 0:
                continue
            if i + b > L:
                continue
            current_s = C[i:i+b]
            if current_s in binary_map[b]:
                num = binary_map[b][current_s]
                if num not in used:
                    new_used = set(used)
                    new_used.add(num)
                    new_count = copy.deepcopy(count_rem)
                    new_count[b] -= 1
                    new_path = path + [num]
                    # Push to stack (using append for DFS, but we process in reverse order)
                    stack.append((i + b, new_used, new_count, new_path))
    return None

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