fork download
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5.  
  6. int first_occurence(vector<int> &arr,int k){
  7. int n = arr.size();
  8. int low=0;
  9. int high = n-1;
  10. int ans=0;
  11.  
  12. while(low<=high){
  13. int mid = (low+high)/2;
  14. if(arr[mid]==k){
  15. ans=mid;
  16. high=mid-1;
  17. }
  18. else{
  19. if(arr[mid]<k){
  20. low=mid+1;}
  21. else{
  22. high=mid-1;
  23. }
  24. }
  25. }
  26.  
  27. return ans;
  28.  
  29. }
  30.  
  31. int last_occurence(vector<int> &arr,int k){
  32. int n = arr.size();
  33. int low=0;
  34. int high = n-1;
  35. int ans=0;
  36.  
  37. while(low<=high){
  38. int mid = (low+high)/2;
  39. if(arr[mid]==k){
  40. ans=mid;
  41. low=mid+1;
  42. }
  43. else{
  44.  
  45. if(arr[mid]<k){
  46. low=mid+1;}
  47. else{
  48. high=mid-1;
  49. }
  50.  
  51. }
  52. }
  53.  
  54. return ans;
  55.  
  56. }
  57. int main() {
  58. // your code goes here
  59. int n,k;
  60. cin>>n>>k;
  61. vector<int> arr(n);
  62. for(int i=0;i<n;i++){
  63. cin>>arr[i];
  64. }
  65.  
  66. int low=0;
  67. int high=n-1;
  68.  
  69. while(low<=high){
  70. int mid = (low+high)/2;
  71.  
  72. int l1 = first_occurence(arr,arr[mid]);
  73. int h1= last_occurence(arr,arr[mid]);
  74.  
  75.  
  76. int a = abs(h1-l1+1);
  77.  
  78. if(a!=k){
  79. cout<<arr[mid]<<endl;
  80. return 0;
  81.  
  82. }
  83. else{
  84. if((h1-low+1)%k==0){
  85. low=h1+1;
  86. }
  87. else{
  88. high=l1-1;
  89. }
  90. }
  91. }
  92.  
  93. cout<<-1<<endl;
  94. return 0;
  95. }
Success #stdin #stdout 0s 5348KB
stdin
11 3

2 2 2 3 3 4 4 4 5 5 5
stdout
3