結果

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

ソースコード

diff # 

import sys
from bisect import bisect_left, bisect_right
from collections import defaultdict

def sum_bit_length(n):
    total = 0
    k = 1
    while (1 << (k-1)) <= n:
        start = 1 << (k-1)
        end = (1 << k) - 1
        if end > n:
            end = n
        if start > end:
            break
        count = end - start + 1
        total += k * count
        k += 1
    return total

def find_N(L):
    low = 1
    high = L
    while low <= high:
        mid = (low + high) // 2
        s = sum_bit_length(mid)
        if s == L:
            return mid
        elif s < L:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def main():
    C = sys.stdin.read().strip()
    L = len(C)
    N = find_N(L)
    
    k_to_strs = defaultdict(dict)
    count = defaultdict(int)
    for x in range(1, N + 1):
        s = bin(x)[2:]
        k = len(s)
        k_to_strs[k][s] = x
        count[k] += 1
    
    sorted_ks = sorted(k_to_strs.keys(), reverse=True)
    result = []
    used = set()
    
    def backtrack(i):
        if i == L:
            return True
        for k in sorted_ks:
            if count[k] == 0:
                continue
            if i + k > L:
                continue
            s = C[i:i+k]
            if s not in k_to_strs[k]:
                continue
            x = k_to_strs[k][s]
            if x in used:
                continue
            used.add(x)
            count[k] -= 1
            result.append(x)
            if backtrack(i + k):
                return True
            result.pop()
            count[k] += 1
            used.remove(x)
        return False
    
    backtrack(0)
    print(' '.join(map(str, result)))

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