逆序对 归并排序

两个局面可互达的充分必要条件是: 逆序对个数的奇偶性相同.
求逆序对个数的算法是归并排序.

时间复杂度

O(n * log(n))

Python 代码

import sys
input = sys.stdin.readline

def mergesort(A):
    if len(A) < 2:
        return A, 0
    n = len(A)
    left, cnt1 = mergesort(A[:n//2])
    right, cnt2 = mergesort(A[n//2:])
    cnt = cnt1 + cnt2
    i, j = 0, 0
    ans = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            ans.append(left[i])
            i += 1
        else:
            cnt += len(left) - i
            ans.append(right[j])
            j += 1
    if i == len(left):
        ans.extend(right[j:])
    else:
        ans.extend(left[i:])
    return ans, cnt


def solve(A, B):
    A.remove(0)
    B.remove(0)
    if A == B:
        print("TAK")
        return
    A, cntA = mergesort(A)
    B, cntB = mergesort(B)
    #print(A, cntA)
    #print(B, cntB)
    if (cntA - cntB) % 2 == 0:
        print("TAK")
    else:
        print("NIE")

while True:
    n = input()
    if not n: break
    n = int(n)
    A = []
    B = []
    for i in range(n):
        A.extend(list(map(int, input().split())))
    for i in range(n):
        B.extend(list(map(int, input().split())))        
    if n == 1:
        print("TAK")
        continue
    solve(A, B)