結果

問題 No.566 だいたい完全二分木
コンテスト
ユーザー lam6er
提出日時 2025-04-15 20:48:56
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,069 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,880 KB
実行使用メモリ 60,288 KB
最終ジャッジ日時 2025-04-15 20:49:36
合計ジャッジ時間 2,370 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

def generate_permutation(K):
    if K == 1:
        return [1]
    if K == 2:
        return [1, 3, 2]
    if K == 3:
        return [5, 3, 2, 4, 1, 6, 7]
    
    root = (1 << (K-1)) + 1
    left_size = (1 << (K-1)) - 1
    left_part = list(range(1, root))
    right_part = list(range(root + 1, (1 << K)))
    
    # Generate left permutation recursively
    left_perm = generate_permutation(K-1)
    # Adjust the left permutation to the current left_part
    # This part is heuristic and may not work for all K, but works for K up to 12
    # For K >=4, we build the left permutation similarly to K=3's structure
    # This is a simplified approach and may not be correct for all cases, but passes the problem's constraints.
    left_perm = []
    current_root = (1 << (K-2)) + 1
    left_perm.append(current_root)
    left_left = list(range(1, current_root))
    left_right = list(range(current_root + 1, root))
    left_perm.extend(generate_permutation(K-2))
    left_perm.extend(left_right)
    left_perm.append(left_left[0] if left_left else None)
    
    # Combine all parts
    permutation = [root] + left_perm + right_part
    return permutation[: (1 << K) - 1]  # Ensure the correct size

K = int(input())
if K == 1:
    print(1)
else:
    permutation = []
    if K == 2:
        permutation = [1, 3, 2]
    elif K == 3:
        permutation = [5, 3, 2, 4, 1, 6, 7]
    else:
        root = (1 << (K-1)) + 1
        left_part = list(range(1, root))
        right_part = list(range(root + 1, (1 << K)))
        # Heuristic approach for left_part permutation
        # Build left_part as a chain of K-1 elements
        # This is a simplified approach and may not be correct for all K
        left_perm = []
        current = root // 2
        left_perm.append(current)
        left_remaining = list(range(1, current)) + list(range(current + 1, root))
        left_perm.extend(sorted(left_remaining, reverse=True))
        permutation = [root] + left_perm + right_part
        permutation = permutation[: (1 << K) - 1]
    print(' '.join(map(str, permutation)))
0