結果

問題 No.3256 Permutation Equation
ユーザー Heartbreak
提出日時 2025-09-06 00:15:54
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 148 ms / 2,000 ms
コード長 1,434 bytes
コンパイル時間 412 ms
コンパイル使用メモリ 82,720 KB
実行使用メモリ 126,752 KB
最終ジャッジ日時 2025-09-06 00:16:06
合計ジャッジ時間 11,603 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

def main():
    N = int(input().strip())
    P_list = list(map(int, input().split()))
    P = [0] + P_list
    C = [0] * (N + 1)
    for i in range(1, N + 1):
        C[i] = P[i] + 1 if P[i] < N else 1
    visited = [False] * (N + 1)
    cbl = {}
    for i in range(1, N + 1):
        if not visited[i]:
            cur = i
            cyc = []
            while not visited[cur]:
                visited[cur] = True
                cyc.append(cur)
                cur = C[cur]
            L = len(cyc)
            cbl.setdefault(L, []).append(cyc)

    B = [0] * (N + 1)
    for L, lists in list(cbl.items()):
        if L % 2 == 1:
            s = (L + 1) // 2
            for cyc in lists:
                for j in range(L):
                    B[cyc[j]] = cyc[(j + s) % L]

    for L, lists in list(cbl.items()):
        if L % 2 == 0:
            if len(lists) % 2 == 1:
                print("No")
                return
            for k in range(0, len(lists), 2):
                x = lists[k]
                y = lists[k + 1]
                for j in range(L):
                    B[x[j]] = y[j]
                    B[y[j]] = x[(j + 1) % L]

    Q = [0] * (N + 1)
    for i in range(1, N + 1):
        bi = B[i]
        if bi == 1:
            Q[i] = N
        else:
            Q[i] = bi - 1

    print("Yes")
    print(" ".join(map(str, Q[1:])))
if __name__ == "__main__":
    main()
0