Count Inversions
Python
Hard
4 views
Problem Description
Read n integers. Use function mergesort_count(arr) to return inversion count and output it.
Input Format
First line n. Second line n integers.
Output Format
One integer inversions.
Official Solution
import sys
sys.setrecursionlimit(1_000_000)
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
def sort_count(arr):
ln=len(arr)
if ln<=1:
return arr,0
mid=ln//2
left,inv1=sort_count(arr[:mid])
right,inv2=sort_count(arr[mid:])
i=0
j=0
inv=inv1+inv2
out=[]
while i<len(left) and j<len(right):
if left[i]<=right[j]:
out.append(left[i]); i+=1
else:
out.append(right[j]); j+=1
inv += len(left)-i
if i<len(left):
out.extend(left[i:])
if j<len(right):
out.extend(right[j:])
return out,inv
_,ans=sort_count(a)
sys.stdout.write(str(ans))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!