結果

問題 No.1779 Magical Swap
コンテスト
ユーザー flippergo
提出日時 2026-07-25 08:52:40
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 1,276 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 232 ms
コンパイル使用メモリ 95,728 KB
実行使用メモリ 120,576 KB
最終ジャッジ日時 2026-07-25 08:52:47
合計ジャッジ時間 4,945 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 16 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def rfind(i):
    if T[i][0]==i:
        return i
    return rfind(T[i][0])
def runion(i,j):
    ri = rfind(i)
    rj = rfind(j)
    if ri==rj:return
    if T[ri][1]>=T[rj][1]:
        T[rj][0] = ri
        T[ri][1] += T[rj][1]
    else:
        T[ri][0] = rj
        T[rj][1] += T[ri][1]
S = int(input())
for _ in range(S):
    N = int(input())
    A = [0]+list(map(int,input().split()))
    B = [0]+list(map(int,input().split()))
    T = [[i,1] for i in range(N+1)]
    visited = [False for _ in range(N+1)]
    for i in range(2,N+1):
        if visited[i]:continue
        if i>2 and 2*i<=N:
            runion(2,i)
        for j in range(i*i,N+1,i):
            runion(i,j)
    col = [-1 for _ in range(N+1)]
    col[1] = 0
    cnt = 1
    for i in range(2,N+1):
        if col[i]>=0:continue
        ri = rfind(i)
        if col[ri]<0:
            col[ri] = cnt
            cnt += 1
        col[i] = col[ri]
    C = {i:[] for i in range(cnt)}
    D = {i:[] for i in range(cnt)}
    for i in range(1,N+1):
        ri = rfind(i)
        C[col[ri]].append(A[i])
        D[col[ri]].append(B[i])
    flag = "Yes"
    for c in range(1,cnt):
        C[c] = sorted(C[c])
        D[c] = sorted(D[c])
        if C[c]!=D[c]:
            flag = "No"
            break
    print(flag)
0