結果
問題 | No.1115 二つの数列 / Two Sequences |
ユーザー |
|
提出日時 | 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 |
ソースコード
#!/usr/bin/env pypy3def merge_list(left,right):result = list()i,j = 0,0inv_count = 0while i < len(left) and j < len(right):if left[i] <= right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1inv_count += (len(left)-i)result += left[i:]result += right[j:]return result,inv_countdef sort_and_count(array):if len(array) <= 1:return array, 0middle = len(array) // 2left,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, countdef count_inversions(arr):_, ret = sort_and_count(arr)return retinput()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] = iA = list(map(translation.get, A))print(count_inversions(A))