結果

問題 No.1115 二つの数列 / Two Sequences
ユーザー xuanji
提出日時 2020-07-17 21:46:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 287 ms / 2,000 ms
コード長 1,037 bytes
コンパイル時間 774 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 111,076 KB
最終ジャッジ日時 2024-11-29 23:04:04
合計ジャッジ時間 6,331 ms
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#!/usr/bin/env pypy3
def merge_list(left,right):
result = list()
i,j = 0,0
inv_count = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
inv_count += (len(left)-i)
result += left[i:]
result += right[j:]
return result,inv_count
def sort_and_count(array):
if len(array) <= 1:
return array, 0
middle = len(array) // 2
left,inv_left = sort_and_count(array[:middle])
right,inv_right = sort_and_count(array[middle:])
merged, count = merge_list(left,right)
count += (inv_left + inv_right)
return merged, count
def count_inversions(arr):
_, ret = sort_and_count(arr)
return ret
input()
A = input().split(' ')
A = list(map(int, A))
B = input().split(' ')
B = list(map(int, B))
translation = dict()
for i, b in enumerate(B):
translation[b] = i
A = list(map(translation.get, A))
print(count_inversions(A))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0