SHARE
TWEET

Untitled

a guest Sep 18th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def get_damages(H):
  2.     '''
  3.     Input:  H | list of bricks per house from west to east
  4.     Output: D | list of damage per house from west to east
  5.     '''
  6.     D = [1 for _ in H]
  7.     ##################
  8.     # YOUR CODE HERE #
  9.     ##################
  10.     house_orderer = [[house, index, 1] for index, house in enumerate(H)]
  11.  
  12.     def helper(A, low=0, high=None):
  13.         if high is None:
  14.             high = len(A)-1
  15.         if 1 < high - low:
  16.             mid = (low + high + 1) // 2
  17.             # Sort sublists
  18.             helper(A, low, mid)
  19.             helper(A, mid, high)
  20.  
  21.             # Merge process starts here
  22.             L, R = A[low:mid], A[mid:high]
  23.             i, j = len(L)-1,len(R)-1
  24.  
  25.             # Check to see damages for each house, and add values to damage array
  26.             while i >= 0 and j>=0:
  27.                 if L[i] > R[j]:
  28.                     L[i][2] += len(R[:j+1])
  29.                     A[high] = L[i]
  30.                     i -= 1
  31.                 else:
  32.                     A[high] = R[j]
  33.                     j -= 1
  34.             while i >= 0:
  35.                 A[high] = L[i]
  36.                 i -=1
  37.                 high -= 1
  38.             while j >= 0:
  39.                 A[high] = R[j]
  40.                 j -=1
  41.                 high -=1
  42.  
  43.             # while low < high:
  44.             #     if (j >= len(R)) or (i < len(L) and L[i][0] < R[j][0]):
  45.             #         A[low] = L[i]
  46.             #         i += 1
  47.             #     else:
  48.             #         A[low] = R[j]
  49.             #         D[i] += len(R[:j])
  50.             #         j += 1
  51.             #     low += 1
  52.  
  53.     helper(house_orderer)
  54.     print(house_orderer)
  55.     print(D)
  56.     return D
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top