結果

問題 No.3109 Swap members
ユーザー h tsuneki
提出日時 2025-04-18 23:58:00
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,852 bytes
コンパイル時間 745 ms
コンパイル使用メモリ 11,904 KB
実行使用メモリ 39,104 KB
最終ジャッジ日時 2025-04-18 23:58:20
合計ジャッジ時間 17,695 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33 WA * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

def can_rearrange(n, k, s, t):
    """
    Determine if it's possible to rearrange the array s to match array t
    using only swaps of elements at positions i and i+k.
    
    Args:
        n: Number of elements
        k: Swap distance
        s: Initial arrangement
        t: Target arrangement
    
    Returns:
        True if possible, False otherwise
    """
    # Check if t is a permutation of s
    if sorted(s) != sorted(t):
        return False
    
    # The key insight: this operation creates a permutation that can be broken down
    # into cycles where elements move by multiples of gcd(k, n)
    
    # Create a mapping from username to position in the target array
    target_positions = {name: i for i, name in enumerate(t)}
    
    # Mark visited positions
    visited = [False] * n
    
    # Check each cycle
    for i in range(n):
        if visited[i]:
            continue
        
        # Start a new cycle
        cycle_positions = set()
        pos = i
        
        # Trace the cycle
        while not visited[pos]:
            visited[pos] = True
            cycle_positions.add(pos)
            
            # Find where the current element should go
            target_pos = target_positions[s[pos]]
            pos = target_pos
        
        # For a cycle to be achievable, all positions in the cycle must be
        # congruent modulo gcd(k, n)
        if len(set(pos % gcd(k, n) for pos in cycle_positions)) > 1:
            return False
    
    return True

def gcd(a, b):
    """Calculate the greatest common divisor of a and b."""
    while b:
        a, b = b, a % b
    return a

# Read input
n, k = map(int, input().split())
s = [input() for _ in range(n)]
t = [input() for _ in range(n)]

# Solve the problem
result = can_rearrange(n, k, s, t)

# Output the result
print("Yes" if result else "No")
0