fork download
copy 
  1. # Time Complexity O(wlogw)
  2.  
  3. from bisect import *
  4.  
  5. def getRange(lval, rval, a): # returns (leftmost occurrence of lval, rightmost occurrence of rval)
  6. 	# 'Find leftmost item greater than or equal to x'
  7. 	i = bisect_left(a, lval)
  8. 	# 'Find rightmost value less than or equal to x'
  9. 	j = bisect_right(a, rval)-1
  10. 	return (i, j)
  11.  
  12.  
  13. def calMod(val, l, r, a): # calculate abs(a[l]-val) + abs(a[l+1]-val) ... abs(a[r-1]-val) + abs(a[r]-val) in log(w)
  14. 	if a[r] <= val:
  15. 		return abs(getSum(a, l, r) - val*(r-l+1))
  16. 	elif a[l] >= val :
  17. 		return abs(getSum(a, l, r) - val*(r-l+1))
  18. 	else:
  19. 		# 'Find rightmost value less than or equal to x'
  20. 		j = bisect_right(a, val)-1
  21. 		# return calMod(val, l, j, a) + calMod(val, j+1, r, a)
  22. 		return abs(getSum(a, l, j) - val*(j-l+1)) + abs(getSum(a, j+1, r) - val*(r-j))
  23.  
  24.  
  25.  
  26. def getSum(a, l, r): # calculate a[l] + a[l+1] ... a[r-1] + a[r] in O(1)
  27. 	return total - (left_sum[l-1] if l else 0) - (right_sum[r+1] if r+1 < len(right_sum) else 0)
  28.  
  29. t = int(input())
  30.  
  31. for ti in range(t):
  32. 	w, n = [int(var) for var in input().split()]
  33. 	a = [int(var) for var in input().split()]
  34.  
  35. 	a.sort();ans = float("inf")
  36.  
  37. 	total = sum(a)
  38.  
  39. 	left_sum, right_sum = a[:], a[:]
  40.  
  41. 	for i in range(1, w):
  42. 		left_sum[i] += left_sum[i-1]
  43.  
  44. 	for i in reversed(range(w-1)):
  45. 		right_sum[i] += right_sum[i+1]
  46.  
  47. 	for v in a:
  48. 		lval, rval = max(1, (2*v - n)/2), min(n, (2*v + n)/2)
  49. 		l,r = getRange(lval, rval, a)
  50. 		moves = calMod(v, l, r, a)
  51. 		if l : 
  52. 			moves += abs(calMod(v, 0, l-1, a) - l*n)
  53. 		if w-(r+1):
  54. 			moves += abs(calMod(v, r+1, w-1, a) - (w-r-1)*n)
  55. 		ans = min(ans, moves)
  56.  
  57. 	print("Case #%d: %d"%(ti+1, ans))
  58.  
Runtime error #stdin #stdout #stderr 0.11s 23596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "./prog.py", line 29, in <module>
EOFError: EOF when reading a line
https://ideone.com/RbfXkV
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!