Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def get_damages(H):
- '''
- Input: H | list of bricks per house from west to east
- Output: D | list of damage per house from west to east
- '''
- D = [1 for _ in H]
- ##################
- # YOUR CODE HERE #
- ##################
- house_orderer = [[house, index, 1] for index, house in enumerate(H)]
- def helper(A, low=0, high=None):
- if high is None:
- high = len(A)-1
- if 1 < high - low:
- mid = (low + high + 1) // 2
- # Sort sublists
- helper(A, low, mid)
- helper(A, mid, high)
- # Merge process starts here
- L, R = A[low:mid], A[mid:high]
- i, j = len(L)-1,len(R)-1
- # Check to see damages for each house, and add values to damage array
- while i >= 0 and j>=0:
- if L[i] > R[j]:
- L[i][2] += len(R[:j+1])
- A[high] = L[i]
- i -= 1
- else:
- A[high] = R[j]
- j -= 1
- while i >= 0:
- A[high] = L[i]
- i -=1
- high -= 1
- while j >= 0:
- A[high] = R[j]
- j -=1
- high -=1
- # while low < high:
- # if (j >= len(R)) or (i < len(L) and L[i][0] < R[j][0]):
- # A[low] = L[i]
- # i += 1
- # else:
- # A[low] = R[j]
- # D[i] += len(R[:j])
- # j += 1
- # low += 1
- helper(house_orderer)
- print(house_orderer)
- print(D)
- return D
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement