結果

問題 No.2254 Reverse Only
ユーザー qwewe
提出日時 2025-05-14 13:03:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,550 bytes
コンパイル時間 302 ms
コンパイル使用メモリ 82,620 KB
実行使用メモリ 158,972 KB
最終ジャッジ日時 2025-05-14 13:05:08
合計ジャッジ時間 14,501 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import Counter

# Set higher recursion depth limit if needed, although default 1000 is likely sufficient for N=2e5
# The required depth is log2(N), which is small. Example: log2(2e5) ~ 17.6.
# sys.setrecursionlimit(200010) 

# Function to count inversions using merge sort logic.
# An inversion is a pair (i, j) such that i < j and arr[i] > arr[j].
# The function returns the sorted array (as a side effect of merge sort) 
# and the total count of inversions.
def count_inversions_mergesort(arr):
    """
    Counts inversions in an array using merge sort algorithm.
    Time complexity: O(N log N)
    Space complexity: O(N) due to merge step needing auxiliary space.
    """
    n = len(arr)
    # Base case: An array with 0 or 1 element has 0 inversions.
    if n <= 1:
        return arr, 0
    
    mid = n // 2
    # Recursively sort and count inversions in left and right halves.
    # Slicing creates copies, ensuring original array/subarrays aren't modified by sibling calls.
    left_arr = arr[:mid]
    right_arr = arr[mid:]
    
    left_sorted, inv_left = count_inversions_mergesort(left_arr)
    right_sorted, inv_right = count_inversions_mergesort(right_arr)
    
    # Merge the two sorted halves and count inversions between them.
    merged = []
    inv_merge = 0
    i, j = 0, 0  # Pointers for left_sorted and right_sorted arrays
    
    len_left = len(left_sorted)
    len_right = len(right_sorted)

    # Merge process
    while i < len_left and j < len_right:
        if left_sorted[i] <= right_sorted[j]:
            # Element from left is smaller or equal, append it. No inversion here.
            merged.append(left_sorted[i])
            i += 1
        else:
            # Element from right is smaller. This means it forms inversions
            # with all the remaining elements in the left_sorted array.
            merged.append(right_sorted[j])
            inv_merge += len_left - i 
            j += 1
    
    # Append any remaining elements from left or right arrays (one must be empty).
    merged.extend(left_sorted[i:])
    merged.extend(right_sorted[j:])
    
    # Total inversions = inversions within left + inversions within right + inversions between halves.
    return merged, inv_left + inv_right + inv_merge

def solve():
    # Read N and K
    N, K = map(int, sys.stdin.readline().split())
    # Read arrays A and B
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))

    # Necessary condition: A and B must be permutations of each other.
    # Check using frequency counts (Counter). This is O(N) on average.
    if Counter(A) != Counter(B):
        print("No")
        return

    # Optimization: If A is already equal to B, 0 operations suffice.
    if A == B:
        print("Yes")
        return

    # Case 1: k > N
    # No operation is possible because minimum length k exceeds array length N.
    # Since A != B, transformation is impossible.
    if K > N:
         print("No")
         return

    # Case 2: k = N
    # The only possible operation is reversing the entire array A[1...N].
    # The only reachable states from A are A itself and A reversed.
    # We already know A != B. Check if B is the reversed version of A.
    if K == N:
        if B == A[::-1]: # Check if B equals A reversed
            print("Yes")
        else:
             print("No") 
        return

    # Case 3: k < N
    # Need to consider the properties of permutations generated by reversals of length >= k.
    # The key property is parity. A reversal of length L changes permutation parity if floor(L/2) is odd.
    # This corresponds to L mod 4 being 2 or 3.
    # If all allowed reversal lengths L (k <= L <= N) correspond to even permutations (L mod 4 is 0 or 1),
    # then only states with the same permutation parity are reachable.
    
    # Calculate inversion counts for A and B to determine their parities.
    # We pass copies `[:]` to count_inversions_mergesort to avoid side effects if needed elsewhere.
    _, inv_A = count_inversions_mergesort(A[:]) 
    _, inv_B = count_inversions_mergesort(B[:])
    
    # Parity is inversion count modulo 2. 0 for even, 1 for odd.
    parity_A = inv_A % 2
    parity_B = inv_B % 2
    
    # Determine if only even permutations can be generated.
    # This happens if and only if for ALL L such that k <= L <= N, L satisfies L % 4 == 0 or L % 4 == 1.
    # This condition simplifies to: (k % 4 == 0 AND N = k + 1) OR (k % 4 == 1 AND N = k) 
    # Since we are in case k < N, the second part (N=k) is impossible.
    # So we only check the first part: k divisible by 4 AND N is exactly k+1.
    only_even_possible = (K % 4 == 0 and N == K + 1)
    
    if only_even_possible:
        # If only even permutations can be generated, the parities of A and B must match.
        if parity_A != parity_B:
            # Parities differ, impossible to reach B from A.
            print("No")
        else:
            # Parities match, assumed reachable.
            print("Yes")
    else:
        # If odd permutations can be generated (i.e., there exists some allowed length L
        # such that L % 4 == 2 or L % 4 == 3), then the group generated typically becomes 
        # large enough (often the full symmetric group S_N or alternating group A_N combined 
        # with one odd permutation allows reaching everything).
        # In these cases, reachability is guaranteed provided A and B are permutations.
        print("Yes")

# Execute the main solve function
solve()
0