fork download
copy 
  1. #include "assert.h"
  2. #include <algorithm>
  3. #include <bitset>
  4. #include <cctype>
  5. #include <cmath>
  6. #include <cstdio>
  7. #include <deque>
  8. #include <functional>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <map>
  12. #include <queue>
  13. #include <set>
  14. #include <sstream>
  15. #include <stack>
  16. #include <stdio.h>
  17. #include <stdlib.h>
  18. #include <string>
  19. #include <string.h>
  20. #include <time.h>
  21. #include <vector>
  22.  
  23. using namespace std;
  24.  
  25. #if LOCAL
  26. 	#define DO_NOT_SEND
  27. #endif
  28.  
  29. typedef long long LL;
  30.  
  31. int IntMaxVal = (int) 1e20;
  32. int IntMinVal = (int) -1e20;
  33. LL LongMaxVal = (LL) 1e20;
  34. LL LongMinVal = (LL) -1e20;
  35.  
  36. #define FOR(i, a, b) for(int i = a; i < b ; ++i)
  37. #define FORD(i, a, b) for(int i = a; i >= b; --i)
  38.  
  39. template<typename T> inline void minimize(T &a, T b) { a = std::min(a, b); }
  40. template<typename T> inline void maximize(T &a, T b) { a = std::max(a, b); }
  41.  
  42. template<typename T> inline void swap(pair<T, T> &p) { swap(p.first , p.second ); }
  43.  
  44. #define all(v) v.begin(),v.end()
  45.  
  46. #define endl '\n'
  47. template<typename T> struct argument_type;
  48. template<typename T, typename U> struct argument_type<T(U)> { typedef U type; };
  49. #define next(t, i) argument_type<void(t)>::type i; cin >> i;
  50.  
  51. template <typename T1, typename T2> istream& operator >>(istream& is, pair<T1, T2>& s) { is >> s.first >> s.second; return is; }
  52. template <typename T> ostream& operator << (ostream& os, const vector<T> &v) { for (int i = 0 ; i < v.size() ; i++) { if (i) os << ' '; os << v[i]; } os << endl; return os; }
  53. template <typename T1, typename T2> ostream& operator << (ostream& os, const vector<pair<T1, T2>> &v) { for (int i = 0 ; i < v.size() ; i++) { os << v[i] << endl; } return os; }
  54. template <typename T1, typename T2> ostream& operator <<(ostream& s, const pair<T1, T2>& t) { s << t.first << ' ' << t.second; return s; }
  55. template <typename T> vector<T> readVector(int n) { vector<T> res(n); for (int i = 0 ; i < n ; i++) cin >> res[i]; return res; }
  56.  
  57. vector<int> get_min_bombing(vector<int> xs, bool reversed) {
  58. 	sort(all(xs));
  59. 	if (reversed) {
  60. 		for (auto &x : xs) x = 1e9 - x;
  61. 		reverse(all(xs));
  62. 	}
  63.  
  64. 	vector<int> ans(xs.size());
  65.  
  66. 	int ptr = 0;
  67.  
  68. 	FOR (i, 1, xs.size()) {
  69. 		while (ptr + 1 < i && max(ans[ptr] + 1, xs[i] - xs[ptr]) > max(ans[ptr + 1] + 1, xs[i] - xs[ptr + 1])) ptr++;
  70. 		ans[i] = max(ans[ptr] + 1, xs[i] - xs[ptr]);
  71. 	}
  72.  
  73. 	if (reversed) {
  74. 		reverse(all(ans));
  75. 	}
  76.  
  77. 	return ans;
  78. }
  79.  
  80. int main() {
  81. 	#ifndef LOCAL
  82. 	freopen("angry.in", "rt", stdin);
  83. 	freopen("angry.out", "wt", stdout);
  84. 	#endif
  85.  
  86. 	srand (time(NULL));
  87. 	ios_base::sync_with_stdio(false); cin.tie(NULL);
  88. 	fixed(cout); cout << setprecision(1);
  89.  
  90. 	next(int, n);
  91. 	auto xs = readVector<int>(n);
  92.  
  93. 	auto l = get_min_bombing(xs, false);
  94. 	auto r = get_min_bombing(xs, true);
  95.  
  96. 	sort(all(xs));
  97.  
  98. 	double ans = r.front();
  99. 	FOR (i, 0, n) minimize(ans, (double) max(l[i] , r[i]));
  100.  
  101. 	int left = 0;
  102. 	int right = n - 1;
  103.  
  104. 	while (left < right) {
  105. 		minimize(ans, max((xs[right] - xs[left]) / 2.0 , (double)(1 + max(l[left] , r[right]))));
  106.  
  107. 		if (l[left + 1] < r[right - 1]) left++;
  108. 		else right--;
  109. 	}
  110.  
  111. 	cout << ans;
  112. }
Runtime error #stdin #stdout #stderr 0s 3456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure'
  what():  basic_filebuf::underflow error reading the file
https://ideone.com/TAlUTn
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!