結果

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

ソースコード

diff # 

import sys
from sys import stdin

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

def find_n(L):
    left = 1
    right = 2 * 10**5  # A safe upper bound
    while left <= right:
        mid = (left + right) // 2
        s = compute_sum(mid)
        if s == L:
            return mid
        elif s < L:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def main():
    C = stdin.read().strip()
    L = len(C)
    N = find_n(L)
    if N == -1:
        print("No solution found")
        return
    
    # Precompute binary representations
    bin_dict = {}
    for x in range(1, N+1):
        s = bin(x)[2:]  # Convert to binary without '0b'
        bin_dict[s] = x
    
    # Now, perform backtracking to find the permutation
    used = set()
    path = []
    found = False

    def backtrack(pos):
        nonlocal found
        if pos == L:
            print(' '.join(map(str, path)))
            found = True
            return
        if found:
            return
        # Try all possible binary strings starting at pos
        # Check all possible lengths l in bin_dict
        for s in bin_dict:
            l = len(s)
            if pos + l > L:
                continue
            if C[pos:pos+l] == s:
                x = bin_dict[s]
                if x not in used:
                    used.add(x)
                    path.append(x)
                    backtrack(pos + l)
                    if found:
                        return
                    path.pop()
                    used.remove(x)
    
    backtrack(0)
    if not found:
        print("No solution found")

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