fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n;
  10. 	cin >> n;
  11.  
  12. 	vector<pair<int, int>> a(n);
  13.  
  14. 	for(int i = 0; i < n; i++){
  15. 		cin >> a[i].first;
  16. 		a[i].second = i;
  17. 	}
  18. 	if(n == 1){
  19. 		cout << 0 << "\n";
  20. 		return;
  21. 	}
  22. 	sort(a.begin(), a.end());
  23. 	int s = a[0].first + 1, e = a[n - 1].first;
  24. 	int ans = a[n - 1].first - a[0].first;
  25.  
  26. 	while(s <= e){
  27. 		ll mid = s + (e - s) / 2;
  28. 		set<pair<int, int>> p, q;
  29. 		vector<int> b(n);
  30. 		for(int i = 0; i < n; i++){
  31. 			if(a[i].first < mid){
  32. 				p.insert({a[i].second, mid - a[i].first});
  33. 				b[a[i].second] = a[i].first;
  34. 			}else if(a[i].first > mid){
  35. 				int extra = a[i].first - mid;
  36. 				q.insert({-a[i].second, extra});
  37. 				b[a[i].second] = mid;
  38. 			}else{
  39. 				b[a[i].second] = a[i].first;
  40. 			}
  41. 		}
  42. 		while(p.size() && q.size()){
  43. 			auto [g, h] = *(q.begin());
  44. 			g = -g;
  45. 			auto [l, r] = *(p.begin());
  46. 			if(g > l){
  47. 				q.erase(q.find({-g, h}));
  48. 			}else{
  49. 				if(h >= r){
  50. 					p.erase(p.find({l, r}));
  51. 					q.erase(q.find({-g, h}));
  52. 					b[l] += r;
  53. 					h -= r;
  54. 					if(h > 0)q.insert({-g, h});
  55. 				}else{
  56. 					p.erase(p.find({l, r}));
  57. 					q.erase(q.find({-g, h}));
  58. 					b[l] += h;
  59. 					r -= h;
  60. 					p.insert({l, r});
  61.  
  62. 				}
  63. 			}
  64.  
  65. 		}
  66. 		for(auto [x, y]: q){
  67. 			b[-x] += y;
  68. 		}
  69. 		sort(b.begin(), b.end());
  70. 		if(mid == 2){
  71. 			for(auto x: b){
  72. 				cout << x << " ";
  73. 			}
  74. 			cout << "\n";
  75. 		}
  76. 		if(b[0] >= mid){
  77. 			ans = min(ans, b[n - 1] - b[0]);
  78. 			s = mid + 1;
  79. 		}else{
  80. 			e = mid - 1;
  81. 		}
  82. 	}
  83. 	cout << ans << "\n";
  84.  
  85. }
  86.  
  87. int main(){
  88. 	ios_base::sync_with_stdio(false);
  89. 	cin.tie(nullptr);
  90.  
  91. 	int t = 1;
  92. 	cin >> t;
  93.  
  94. 	for(int i = 1; i <= t; i++){
  95. 		solve();
  96. 	}
  97. 	return 0;
  98. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin
copy 
1
4
4 2 3 1
stdout
copy 
2 2 2 4 
2
https://ideone.com/9cvdUN
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

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!