fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 3e5 + 5;   
  11.  
  12. int n;   
  13. int a[N], b[N];  
  14.  
  15. bool check(int mid) {
  16. 	b[1] = a[1] - mid;  
  17. 	int prv = b[1]; 
  18. 	for (int i = 2; i <= n; i++) {
  19. 		b[i] = max(prv + 1, a[i] - mid);
  20. 		if (b[i] > a[i] + mid) return false;  
  21. 		prv = b[i];  
  22. 	}
  23. 	return true; 
  24. }
  25.  
  26. int main() {
  27. 	ios::sync_with_stdio(0); cin.tie(0);  	
  28. 	cin >> n; 
  29. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  30.  
  31. 	int l = 0, r = 1e9, ans = -1;  
  32. 	while (l <= r) {
  33. 		int mid = (l + r) >> 1;  
  34.  
  35. 		if (check(mid)) {
  36. 			ans = mid;    
  37. 			r = mid - 1;  
  38. 		}
  39. 		else {
  40. 			l = mid + 1;  
  41. 		}
  42. 	}
  43.  
  44. 	check(ans); 
  45.  
  46. 	cout << ans << '\n';  
  47. 	for (int i = 1; i <= n; i++) cout << b[i] << ' '; cout << '\n'; 
  48. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
3
3 2 1
stdout
copy 
2
1 2 3
https://ideone.com/252NXY
language:
C++14 (gcc 8.3)
created:
1 year 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!