ARC120 Swap2[python]

URL

구속

문제 개요

코드 커밋

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a_ = [i+a[i] for i in range(n)]
b_ = [i+b[i] for i in range(n)]
if set(a_) != set(b_):
    print(-1)
    exit()
dict_b = defaultdict(list)
c = [0]*n
for i in range(n):
    dict_b[b_[i]].append(i)
# print(dict_b)
a_count = {}  # a の要素に対して何回出てきたか
for i in range(n):
    if a_[i] in a_count:
        a_count[a_[i]] += 1
    else:
        a_count[a_[i]] = 0
    #print(dict_b[a_[i]], a_count[a_[i]])
    c[i] = dict_b[a_[i]][a_count[a_[i]]]
# c に関して転倒数の計算


def mergecount(A):
    cnt = 0
    n = len(A)
    if n > 1:
        A1 = A[:n >> 1]
        A2 = A[n >> 1:]
        cnt += mergecount(A1)
        cnt += mergecount(A2)
        i1 = 0
        i2 = 0
        for i in range(n):
            if i2 == len(A2):
                A[i] = A1[i1]
                i1 += 1
            elif i1 == len(A1):
                A[i] = A2[i2]
                i2 += 1
            elif A1[i1] <= A2[i2]:
                A[i] = A1[i1]
                i1 += 1
            else:
                A[i] = A2[i2]
                i2 += 1
                cnt += n//2 - i1
    return cnt


print(mergecount(c))

고찰하다.

실시 방침

다음의 반성

참고 자료