fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. int max_index_in_bitonic_array(vector<int> A){
  6.     int low = 0;
  7.     int high = A.size() - 1;
  8.     while(low <= high){
  9.         int mid = low + (high - low) / 2;
  10.         if((A[mid] > A[mid - 1]) && (A[mid] > A[mid + 1])){
  11.             return mid;
  12.         }
  13.         if(A[mid] < A[mid - 1] && A[mid] > A[mid + 1]){
  14.             // max element lies on left
  15.             high = mid + 1;
  16.         }
  17.         else{
  18.             // max element lies on right
  19.             low = mid - 1;
  20.         }
  21.     }
  22. }
  23.  
  24.  
  25.  
  26. int binary_search(int low, int high, vector<int> A, int B){
  27.     while(low <= high){
  28.         int mid = low + (high - low) / 2;
  29.         if(A[mid] == B){
  30.             return mid;
  31.         }
  32.         if(A[mid] < B){
  33.             low = mid + 1;
  34.         }
  35.         if(A[mid] > B){
  36.             high = mid - 1;
  37.         }
  38.     }
  39.     return -1;
  40. }
  41.  
  42.  
  43. int solve(vector<int> &A, int B) {
  44.     // Find the max point in the array
  45.     int max_index = max_index_in_bitonic_array(A);
  46.     cout<<max_index<<endl;
  47.  
  48.     // Perform 2 binarcy searches
  49.     int result = binary_search(0, max_index, A, B);
  50.     cout<<result<<endl;
  51.     if(result == -1){
  52.         return binary_search(max_index + 1, A.size(), A, B);
  53.     }
  54.     return result;
  55. }
  56.  
  57. int main() {
  58. 	// your code goes here
  59. 	vector<int> a;
  60. 	// 1, 2, 3, 4, 5, 10, 9, 8, 7, 6
  61. 	// 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11 
  62. 	a.push_back(1);
  63. 	a.push_back(2);
  64. 	a.push_back(3);
  65. 	a.push_back(4);
  66. 	a.push_back(5);
  67. 	a.push_back(6);
  68. 	a.push_back(7);
  69. 	a.push_back(8);
  70. 	a.push_back(9);
  71. 	a.push_back(10);
  72. 	a.push_back(20);
  73. 	a.push_back(19);
  74. 	a.push_back(18);
  75. 	a.push_back(17);
  76. 	a.push_back(16);
  77. 	a.push_back(15);
  78. 	a.push_back(14);
  79. 	a.push_back(13);
  80. 	a.push_back(12);
  81. 	a.push_back(11);
  82.  
  83. 	cout<<solve(a, 12);
  84.  
  85. 	return 0;
  86. }
Success #stdin #stdout 0.01s 5468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10
-1
-1
https://ideone.com/h1JRrf
language:
C++14 (gcc 8.3)
created:
2 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!