Page MenuHomec4science
Files F103562362

elves.py
No OneTemporary
Actions

File Metadata

Created
Mon, Mar 3, 00:25

elves.py
View Options

#!/usr/bin/python
def merge_count(L, R):
# sizes
nl = len(L)
nr = len(R)
# append sentinels
L.append(float('inf'))
R.append(float('inf'))
# counter
c = 0
# output list
out = []
# indices
l = 0
r = 0
# loop over and sort
while l < nl or r < nr:
if R[r] < L[l]:
out.append(R[r])
r += 1
if l < nl: # exclude sentinel case
#inversion detected
#print("Inversion detected: (%f, %f)" % (L[l], R[r]))
c += nl - l
else:
out.append(L[l])
l += 1
return c, out
def merge_count_sort(L):
n = len(L)
if n <= 1:
return 0, L
half = n // 2
c1, L1 = merge_count_sort(L[0:half])
c2, L2 = merge_count_sort(L[half:n])
#print("L1 = ", L1)
#print("L2 = ", L2)
c, Lout = merge_count(L1, L2)
#print("Count = ", c1 + c2 + c)
return c1 + c2 + c, Lout
def parse_input(fstream):
# first line
line = fstream.readline()
n = int(line) # already parseable
# second line
line = fstream.readline()
A = line.split(' ')
# third line
line = fstream.readline()
B = line.split(' ')
if len(A) != n or len(B) != n:
raise Exception("Input size not corresponding")
# convert into floating point numbers
for i in range(n):
A[i] = float(A[i])
B[i] = float(B[i])
return (n, A, B)
import sys
# main execution
n, A, B = parse_input(sys.stdin)
#print("n = ", n)
#print("A = ", A)
#print("B = ", B)
#print()
# construct paired list
L = [(A[i], B[i]) for i in range(n)]
#print("L = ", L)
# sort by A[i] less criteria
L.sort(key = lambda x: x[0])
#print("L after sort = ", L)
#print()
# redefine B with A's order
B = [L[i][1] for i in range(n)]
A = [L[i][0] for i in range(n)]
#print("List A before count sort: ", A)
#print("List B before count sort: ", B)
#print()
# sort B counting inversions
count, B = merge_count_sort(B)
#print("List B after count sort: ", B)
#print("Inversions counted: ", count)
print(count)

Event Timeline

c4science · Help