結果

問題 No.1743 Permutation Code
ユーザー lam6er
提出日時 2025-03-31 17:52:36
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,968 bytes
コンパイル時間 233 ms
コンパイル使用メモリ 82,672 KB
実行使用メモリ 79,512 KB
最終ジャッジ日時 2025-03-31 17:53:23
合計ジャッジ時間 11,480 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
import math

def main():
    C = stdin.read().strip()
    L = len(C)
    
    # Find B and N
    found = False
    B_found = None
    N_found = None
    for B in range(1, 65):  # Assuming B won't exceed 64
        if B == 1:
            sum_part = 0
        else:
            sum_part = (B-2) * (1 << (B-1)) + 1
        if sum_part > L:
            break
        rest = L - sum_part
        if rest < 0:
            continue
        if rest % B != 0:
            continue
        x = rest // B
        N = x + (1 << (B-1)) - 1
        min_N = 1 << (B-1)
        max_N = (1 << B) - 1
        if min_N <= N <= max_N:
            found = True
            B_found = B
            N_found = N
            break
    if not found:
        # Try B=1
        if L == 1:
            B_found = 1
            N_found = 1
            found = True
    assert found, "No valid B and N found"
    B = B_found
    N = N_found
    
    # Precompute the valid numbers for each bit length
    groups = {}
    for num in range(1, N+1):
        b = num.bit_length()
        if b not in groups:
            groups[b] = set()
        groups[b].add(num)
    
    # Prepare the count for each b
    count = {}
    for b in groups:
        if b < B:
            cnt = 1 << (b-1)
            count[b] = cnt
        else:
            cnt = N - (1 << (b-1)) + 1
            count[b] = cnt
    
    # Now, perform backtracking to split the string
    path = []
    used = set()
    
    from functools import lru_cache
    
    # Since recursion might be too slow for big cases, let's try iterative backtracking
    # But for this example, let's try with memoization and pruning
    
    def dfs(pos):
        if pos == L:
            return True
        # Try all possible b in descending order to pick largest b first
        for b in sorted(groups.keys(), reverse=True):
            if count[b] == 0:
                continue
            if pos + b > L:
                continue
            s = C[pos:pos+b]
            if s[0] == '0':
                continue  # No leading zeros
            num = int(s, 2)
            min_num = 1 << (b-1)
            max_num = (1 << b) -1 if b < B else N
            if not (min_num <= num <= max_num):
                continue
            if num in used:
                continue
            # Check if num is in groups[b]
            if num not in groups[b]:
                continue
            # Proceed with this choice
            used.add(num)
            count[b] -= 1
            path.append(num)
            if dfs(pos + b):
                return True
            path.pop()
            used.remove(num)
            count[b] += 1
        return False
    
    # Initial counts
    original_count = count.copy()
    
    if dfs(0):
        print(' '.join(map(str, path)))
    else:
        # This shouldn't happen as per problem statement
        print("No solution found")
    
if __name__ == '__main__':
    main()
0