fork download 
  1. #include <bits/stdc++.h>
  2. // iostream is too mainstream
  3. #include <cstdio>
  4. // bitch please
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <cstdlib>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <queue>
  12. #include <stack>
  13. #include <list>
  14. #include <cmath>
  15. #include <iomanip>
  16. #include <time.h>
  17. #define dibs reserve
  18. #define OVER9000 1234567890
  19. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  20. #define tisic 47
  21. #define soclose 1e-8
  22. #define chocolate win
  23. // so much chocolate
  24. #define patkan 9
  25. #define ff first
  26. #define ss second
  27. #define abs(x) ((x < 0)?-(x):x)
  28. #define uint unsigned int
  29. #define dbl long double
  30. #define pi 3.14159265358979323846
  31. using namespace std;
  32. // mylittledoge
  33.  
  34. #ifdef DONLINE_JUDGE
  35. 	// palindromic tree is better than splay tree!
  36. 	#define lld I64d
  37. #endif
  38.  
  39. int main() {
  40. 	freopen("angry.in","r",stdin);
  41. 	freopen("angry.out","w",stdout);
  42. 	cin.sync_with_stdio(0);
  43. 	cin.tie(0);
  44. 	cout << fixed << setprecision(10);
  45. 	int N;
  46. 	cin >> N;
  47. 	vector<long long> X(N);
  48. 	for(int i =0; i < N; i++) cin >> X[i];
  49. 	sort(begin(X),end(X));
  50. 	N =unique(begin(X),end(X))-begin(X);
  51. 	X.resize(N);
  52. 	for(int i =0; i < N; i++) X[i] *=2;
  53. 	map<long long,int> Xs;
  54. 	for(int i =0; i < N; i++) Xs[X[i]] =i;
  55.  
  56. 	vector<long long> minRl(N,OVER9000), minRr(N,OVER9000);
  57. 	minRl[0] =-2;
  58. 	for(int i =1; i < N; i++) {
  59. 		long long Ra =-1, Rb =OVER9000;
  60. 		while(Rb-Ra > 1) {
  61. 			long long R =(Ra+Rb)/2;
  62. 			auto it =Xs.lower_bound(X[i]-R);
  63. 			if(it->ss == i) {Ra =R; continue;}
  64. 			if(minRl[it->ss] > R-2) Ra =R;
  65. 			else Rb =R;}
  66. 		minRl[i] =Rb;}
  67. 	minRr[N-1] =-2;
  68. 	for(int i =N-2; i >= 0; i--) {
  69. 		long long Ra =-1, Rb =OVER9000;
  70. 		while(Rb-Ra > 1) {
  71. 			long long R =(Ra+Rb)/2;
  72. 			auto it =Xs.upper_bound(X[i]+R);
  73. 			it--;
  74. 			if(it->ss == i) {Ra =R; continue;}
  75. 			if(minRr[it->ss] > R-2) Ra =R;
  76. 			else Rb =R;}
  77. 		minRr[i] =Rb;}
  78.  
  79. 	long long Ra =-1, Rb =OVER9000;
  80. 	while(Rb-Ra > 1) {
  81. 		long long R =(Ra+Rb)/2;
  82. 		bool ok =false;
  83. 		for(int i =0; i < N; i++) {
  84. 			auto it =Xs.upper_bound(X[i]+2*R);
  85. 			it--;
  86. 			if(max(minRl[i],minRr[it->ss])+2 <= R) ok =true;}
  87. 		if(ok) Rb =R;
  88. 		else Ra =R;}
  89.  
  90. 	cout << Rb/2 << ((Rb%2 == 0)?".0":".5") << "\n";
  91. 	return 0;}
  92.  
  93. // look at my code
  94. // my code is amazing
  95.  
Runtime error #stdin #stdout #stderr 0s 3416KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_filebuf::underflow error reading the file
https://ideone.com/qehes6
language:
C++14 (gcc 8.3)
created:
8 years 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!