fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX = 1000;
  6. int a[MAX];
  7. int n;
  8.  
  9. void swap(int &a, int &b) {
  10. 	int tmp = a;
  11. 	a = b;
  12. 	b = tmp;
  13. }
  14.  
  15. // Rearranges elements of a[l..r] in such a way that first comes elements 
  16. // lower or equal to M, next comes elements greater than M. Elements in each group
  17. // come in no particular order.
  18. // Returns an index of the first element among a[l..r] which is greater than M.
  19. int rearrange(int l, int r, int M) {
  20. 	int i = l, j = r;
  21. 	while (i <= j)
  22. 		if (a[i] <= M) i++;
  23. 		else swap(a[i], a[j--]);
  24. 	return i;
  25. }
  26.  
  27. int main() {
  28. 	cin >> n;
  29. 	for (int i = 0; i < n; i++) cin >> a[i];
  30.  
  31. 	int L = 1, R = 2 * n;
  32. 	int l = 0, r = n - 1;
  33. 	while (L < R) {
  34. 		int M = (L + R) / 2; // pivot element
  35. 		int m = rearrange(l, r, M); 
  36. 		if (m - l == M - L + 1) 
  37. 			l = m, L = M + 1;
  38. 		else
  39. 			r = m - 1, R = M;
  40. 	}
  41.  
  42. 	cout << L;
  43. 	return 0;
  44. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
12
12 7 10 11 9 1 4 3 2 7 6 24 8
stdout
copy 
5
https://ideone.com/x9LQKr
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!