fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. int isP(int m,vector<int>&t,int k){//recieved mid vector of indeces of current element and k 
  5.     int x=0;
  6.     for(int i=1;i<m;i++){ //checking whether the answer is possible for window size m or mid 
  7.         x+=t[i]-t[i-1]-1;
  8.     }
  9.     if(x<=k) //means answer is possible for the first window size itself hence no need to go further
  10.     return 1;
  11.     //if we are not able to get the answer in the first window then we silmply use sliding window to move our window of size m forward
  12.     for(int i=m;i<t.size();i++){
  13.         x+=t[i]-t[i-1]-1;
  14.         x-=t[i-m+1]-t[i-m]-1; //sliding the window
  15.         if(x<=k) //if found a window then return 1 
  16.         return 1;
  17.     }
  18.     return 0;
  19. }
  20.  
  21. void solve(){
  22.  
  23.     // int n;cin>>n;
  24.     // int k;cin>>k;
  25.     // vector<int>v(n);
  26.     int n=8,k=3;
  27.     vector<int> v={1, -2, 1, 1, 3, 2, 1 ,-2};
  28.     map<int,vector<int>>mp;
  29.     //storing all the position of indices of each element in the vector corresponding to that element 
  30.     for(int i=0;i<n;i++){
  31.         // cin>>v[i];
  32.         mp[v[i]].push_back(i);
  33.     }
  34.     int fans = 0;
  35.     //iterating through the keys of the map
  36.     for(auto x:mp){
  37.         vector<int>t=x.second; //storing the vector containing all the positons(indeces) of the current element in vector t 
  38.  
  39.         //Applying Binary Search to to check that whether we are able to get a valid answer for the current window size (mid)
  40.         int l=0;
  41.         int h=t.size();
  42.         int ans =0 ;
  43.  
  44.         while(l<=h){
  45.  
  46.             int mid = (l+h)/2;
  47.             int x = isP(mid,t,k);
  48.             if(x==1) //if answer is valid for the current window size mid(or m) then it might be the case that it is possible for larger size so we increase mid to get a larger window
  49.             {
  50.                 ans = mid;
  51.                 l=mid+1; //continuing further to obtain a better answer or larger window(if possible)
  52.             }
  53.             else{
  54.                 h=mid-1; //else we decrease the window size which we are checking
  55.             }
  56.  
  57.         } 
  58.         fans = max(fans,ans); //updating the answer
  59.     }
  60.  
  61.     cout<<fans<<endl;
  62.  
  63. }
  64. int main()
  65. {
  66.     solve();
  67. return 0;
  68. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/1l5gEs
language:
C++14 (gcc 8.3)
created:
2 days 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!