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=-1;
  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=-1;
  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. int ans=-1;
  69.  
  70. while(low<=high){
  71. int mid = (low+high)/2;
  72.  
  73. int l1 = k*(mid/k);
  74. int h1= l1+k-1;
  75.  
  76. if(h1>=n || arr[l1]!=arr[h1]){
  77. ans=arr[mid];
  78. high=mid-1;
  79. }
  80. else{
  81. low=h1+1;
  82. }
  83. }
  84.  
  85. // if(arr[l1]!=arr[mid]){
  86. // cout<<arr[mid]<<endl;
  87. // return 0;
  88.  
  89. // }
  90.  
  91. // if(l1+k-1<n && arr[h1]!=arr[mid]){
  92. // cout<<arr[mid]<<endl;
  93. // return 0;
  94.  
  95. // }
  96. // int a = abs(h1-l1+1);
  97.  
  98. // if(a!=k){
  99. // cout<<arr[mid]<<endl;
  100. // return 0;
  101.  
  102. // }
  103. // else{
  104. // if((h1-low+1)%k==0){
  105. // low=h1+1;
  106. // }
  107. // else{
  108. // high=l1-1;
  109. // }
  110. // }
  111. // }
  112.  
  113. cout<<ans<<endl;
  114. return 0;
  115. }
Success #stdin #stdout 0.01s 5348KB
stdin
5 3
1 1 2 2 2 
stdout
1