fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3. #define Fors(n) for(int i=1;i<=n;i++)
  4. #define For(n) for(i=0;i<n;i++)
  5. #define ll long long
  6. #define vint(s) vector<int> s
  7. #define pb(x)  push_back(x)
  8. #define mpair(x,y) make_pair(x,y)
  9. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  10.  
  11. bool compare(std::pair<long long, ll> i, pair<ll, ll> j) {
  12.   return i.second > j.second;
  13. }
  14.  
  15.  
  16. ll x=0,y=0,n=0,i=0;
  17.  
  18. int main(){
  19.     IOS;
  20.     ll I;
  21.     // inputs n & I n -->  the length of the array 
  22.     //    I --> the size of the disk in bytes
  23.     cin >> n >> I;
  24.     I *= 8;  // bytes --> bits
  25.     map<ll, ll> mp; 
  26.     set<ll> s;
  27.     ll a[n+1];
  28.     ll k = (I/n );
  29.  
  30.     ll K = 1;    // number of digits I can accomodate
  31.  
  32.     if (k > 28){
  33.     	K = (1<<28);
  34.     }
  35.     else{
  36.     	K = (1<<k);
  37.     }
  38.  
  39.     //cout << K;
  40.     // Loop 0 - (n-1)
  41.     For (n){
  42.     	cin >> a[i];
  43.     	mp[a[i]]++;  // map <ll, ll>
  44.     	s.insert(a[i]); // s is set<long long>
  45.     }
  46.  
  47.     // Logic  if the given space is greater than current distinct integers 
  48.     // then no element need to be change hence answer = 0; 
  49.     if (s.size() <= K){
  50.     	cout << "0" << endl;
  51.     	return 0;
  52.     }
  53.     s.clear();
  54.     vector <pair <ll, ll>> v; // vector pair
  55.  
  56.     // below loop only pshes the map mp's values in vector 
  57.     // v.push_back({map.key,map.value})
  58.     ll pre[n+2];
  59.     pre[0] = 0;
  60.     ll l = 1;
  61.     for (auto it = mp.begin();it!=mp.end();it++){
  62.     	ll f,ss;
  63.     	f = it->first ;
  64.     	ss = it->second ;
  65.     	pre[i] = pre[i-1]+ss;
  66.     	l++;
  67.     }
  68.     ll ans = 0;
  69.     //  we sort vector so according to their second values of pair
  70.     // so that elemnt has maximum number of occurence come first 
  71.  
  72.     //sort(v.begin(),v.end(),compare);
  73.  
  74.     // In the below loop all we do is to count occurences of 
  75.     //  the elemnts we can accomodate 
  76.     // we can only accomodate maxium K distinct numbers
  77.  
  78.     for (i = 0; i < l-K; i++){
  79.     	ans = max(ans,pre[i+K]-pre[i])
  80.     }
  81.     // answer is the numer of elemnts need to be changed is n-ans
  82.     cout << abs(n-ans) << endl;
  83.     return 0;
  84. }
Success #stdin #stdout 0s 4344KB
comments (?)
stdin
copy 
6 1
1 1 2 2 3 3
stdout
copy 
2
https://ideone.com/EXSHX4
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!