結果

問題 No.3529 2p Teleportations
コンテスト
ユーザー kidodesu
提出日時 2026-05-04 23:24:44
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 261 ms / 2,000 ms
コード長 1,399 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 126 ms
コンパイル使用メモリ 85,808 KB
実行使用メモリ 89,724 KB
最終ジャッジ日時 2026-05-04 23:25:03
合計ジャッジ時間 16,709 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def main():
    def made(C):
        l = len(C)
        t = 2 * p % l
        m = pow(t, -1, l)
        for i in range(l):
            B[C[i]] = C[(i-m)%l]
    def made1(C0, C1):
        l = len(C)
        t = p % l
        m = pow(t, -1, l)
        for i in range(l):
            B[C0[i]] = C1[i]
            B[C1[i]] = C0[(i-m)%l]
    def made2(C):
        l = len(C)-1
        t = 2 * p % l
        m = pow(t, -1, l)
        for i in range(l):
            B[C[i]] = C[(i-m)%l]
        B[C[-1]] = C[(0-m)%l]
    n, p = list(map(int, input().split()))
    #A = list(map(lambda x: int(x), input().split()))
    A = list(map(lambda x: int(x)-1, input().split()))
    B = [-1] * n
    D = [[] for _ in range(n+1)]
    for i in range(n):
        if B[i] != -1: continue
        C = []
        s = i
        while B[s] == -1:
            B[s] = -2
            C.append(s)
            s = A[s]
        if len(C) == 1:
            B[i] = i
        elif len(C) % 2:
            made(C)
        else:
            if D[len(C)]:
                made1(C, D[len(C)].pop())
            else:
                D[len(C)].append(C)
    for i in range(n+1):
        if D[i]:
            C = D[i][0]
            if len(C) == 2:
                B[C[0]] = C[0]
                B[C[1]] = C[0]
            else:
                made2(C)
    return B
    
for _ in range(int(input())):
	A = main()
	print(*[a+1 for a in A])
0