fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5.  
  6. bool is_poss(vector<ll> heights,ll start,ll k) {
  7. 	ll level=start+k;
  8. 	for(int i=1;i<heights.size();i++) {
  9. 		if(heights.at(i)<level) {
  10. 			return false;
  11. 		}
  12. 		level+=k;
  13. 	}
  14. 	return true;
  15. }
  16.  
  17.  
  18. int main()
  19. {
  20. 	int t;
  21. 	cin>>t;
  22. 	while(t--) {
  23. 		int n;
  24. 		cin>>n;
  25. 		vector<ll> heights;
  26. 		ll temp;
  27. 		if(n==1) {
  28. 			cin>>temp;
  29. 			cout<<(temp-1)<<' '<<temp<<'\n';
  30. 			continue;
  31. 		}
  32. 		for(int i=0;i<n;i++) {
  33. 			cin>>temp;
  34. 			heights.push_back(temp);
  35. 		}
  36. 		ll low=0;
  37. 		ll high=*max_element(heights.begin(), heights.end());
  38. 		ll mid=low+(high-low+1)/2;
  39. 		while(low<high) {
  40. 			if(is_poss(heights,1,mid)) {
  41. 				low=mid;
  42. 			} else {
  43. 				high=mid-1;
  44. 			}
  45. 			mid=low+(high-low+1)/2;
  46. 		}
  47. 		ll finalk=low;
  48. 		low=1;
  49. 		high=heights.front();
  50. 		mid=low+(high-low+1)/2;
  51. 		while(low<high) {
  52. 			if(is_poss(heights,mid,finalk)) {
  53. 				low=mid;
  54. 			} else {
  55. 				high=mid-1;
  56. 			}
  57. 			mid=low+(high-low+1)/2;
  58. 		}
  59. 		ll finalstart=low;
  60. 		cout<<finalk<<' '<<finalstart<<'\n';
  61. 	}
  62. 	return 0;
  63. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
4
3
1 2 3
3
5 4 3
3
200 150 100
1
8
stdout
copy 
1 1
1 1
49 2
7 8
https://ideone.com/Jo8Pg4
language:
C++14 (gcc 8.3)
created:
5 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!