結果

問題 No.1743 Permutation Code
ユーザー lam6er
提出日時 2025-04-09 21:00:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,156 bytes
コンパイル時間 178 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 77,320 KB
最終ジャッジ日時 2025-04-09 21:02:19
合計ジャッジ時間 10,542 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compute_n(length):
    n = 0
    total = 0
    current_bit_length = 1
    start = 1
    while True:
        end = start * 2 - 1
        if start > n + 1:
            possible_add = n + 1
            if start > possible_add:
                possible_add = start
            count = min(end, possible_add) - start + 1
        else:
            count = end - start + 1
        remaining = length - total
        max_count = remaining // current_bit_length
        if max_count * current_bit_length > remaining:
            max_count = remaining // current_bit_length
        actual_count = min(count, max_count)
        add = actual_count * current_bit_length
        total += add
        n += actual_count
        if total == length:
            return n
        if total > length:
            return -1  # This shouldn't happen as per problem constraints
        start *= 2
        current_bit_length += 1

def main():
    import sys
    C = sys.stdin.read().strip()
    L = len(C)
    
    # Compute N
    n = 0
    total_bits = 0
    current_bit = 1
    start = 1
    while True:
        end = start * 2 - 1
        if start > n + 1:
            next_num = n + 1
            if next_num < start:
                current_start = next_num
            else:
                current_start = start
            current_end = min(end, n + (end - start + 1))
            if current_start > current_end:
                current_count = 0
            else:
                current_count = current_end - current_start + 1
        else:
            current_count = end - start + 1
        remaining = L - total_bits
        max_possible = remaining // current_bit
        if max_possible < 0:
            max_possible = 0
        count = min(current_count, max_possible)
        add_bits = count * current_bit
        total_bits += add_bits
        n += count
        if total_bits == L:
            break
        if total_bits > L:
            n -= (total_bits - L) // current_bit
            break
        start *= 2
        current_bit += 1
    
    # Generate binaries grouped by bit length
    from collections import defaultdict
    binaries = defaultdict(dict)
    for x in range(1, n+1):
        b = bin(x)[2:]
        l = len(b)
        binaries[l][b] = x
    
    # Prepare the result
    result = []
    used = [False]*(n+1)
    length_list = sorted(binaries.keys(), reverse=True)
    
    # Memoization for positions and used x
    memo = {}
    
    def backtrack(pos):
        if pos == L:
            return True
        for l in length_list:
            if l not in binaries:
                continue
            if pos + l > L:
                continue
            substring = C[pos: pos+l]
            if substring in binaries[l]:
                x = binaries[l][substring]
                if not used[x]:
                    used[x] = True
                    result.append(x)
                    if backtrack(pos + l):
                        return True
                    used[x] = False
                    result.pop()
        return False
    
    backtrack(0)
    print(' '.join(map(str, result)))

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