結果

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

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    C = sys.stdin.readline().strip()
    L = len(C)

    # Step 1: Find N such that S(N) = L
    # S(N) is the sum of the binary lengths of 1..N
    N = 0
    S = 0
    while True:
        N += 1
        b = N.bit_length()
        S += b
        if S == L:
            break
        elif S > L:
            # This should not happen as per problem statement
            print("No solution")
            return

    # Precompute binary strings for 1..N
    binary = {i: bin(i)[2:] for i in range(1, N+1)}
    lengths = {i: len(s) for i, s in binary.items()}

    # Now, find a permutation of 1..N such that their binary strings concatenated form C
    # We'll use a backtracking approach
    result = []
    used = [False] * (N + 1)  # 1-based

    def backtrack(pos):
        if pos == L:
            return True
        for k in range(1, N+1):
            if not used[k]:
                s = binary[k]
                l = lengths[k]
                if pos + l > L:
                    continue
                if C[pos:pos+l] == s:
                    used[k] = True
                    if backtrack(pos + l):
                        result.append(k)
                        return True
                    used[k] = False
        return False

    if backtrack(0):
        print(' '.join(map(str, reversed(result))))
    else:
        print("No solution")

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