Advertisement
Guest User

Untitled

a guest
Aug 18th, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.12 KB | None | 0 0
  1. def search(mas, Id, pos):
  2.     l = 0
  3.     r = len(mas)
  4.    
  5.     while (r - l > 1):
  6.         m = (r + l) // 2
  7.         if (mas[m][0] < Id or (mas[m][0] == Id and mas[m][1] < pos)):
  8.             l = m
  9.         else:
  10.             r = m
  11.            
  12.     for i in range(l, r + 1):
  13.         if (mas[i][0] == Id and mas[i][1] == pos):
  14.             return i
  15.    
  16.     return -1
  17.  
  18. def doctorAndPatients(patientId, query):
  19.     N = len(patientId)
  20.     Q = len(query)
  21.    
  22.     assert(1 <= N and N <= 100000)
  23.     assert(1 <= Q and Q <= 100000)
  24.    
  25.     for i in range(N):
  26.         assert(1 <= patientId[i] and patientId[i] <= 100000)
  27.        
  28.     for i in range(Q):
  29.         assert(0 <= query[i] and query[i] < N)
  30.    
  31.     mas = []
  32.     res = []
  33.    
  34.     for i in range(N):
  35.         mas.append((patientId[i], i))
  36.        
  37.     mas.sort()
  38.    
  39.     print(mas)
  40.    
  41.     for i in range(Q):
  42.         pos = search(mas, patientId[query[i]], query[i])
  43.         if (pos + 1 < N and mas[pos + 1][0] == mas[pos][0]):
  44.             res.append(mas[pos + 1][1] - mas[pos][1])
  45.         else:
  46.             res.append(-1)
  47.    
  48.     return res
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement