fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5.  
  6. //<---------------------------------------------useful functions------------------------------------------------>
  7.  
  8. bool is_square(ll x){ll y=sqrt(x);   return (x==(y*y));}
  9. ll lcm(ll x,ll y){return  ((x/__gcd(x,y))*y);}
  10. ll h_pow_2_less_x(ll x){
  11.     if(x==0)        return 0;
  12.     ll y=1;
  13.     while((y*2)<=x)     y=y<<1;
  14.     return y;
  15. }
  16. ll ceil_div(ll x,ll y){return ((x/y)+((x%y)!=0));}      //returns ceil(x/y);
  17.  
  18. //<---------------------------------------------useful functions------------------------------------------------>
  19.  
  20. void run_case(){
  21.     int i,n,ans=0,j;
  22.     cin>>n;
  23.     vector<int>v(n);
  24.     set<pair<int,int>>pos;
  25.     pair<int,int>p;
  26.     for(i=0;i<n;i++)        cin>>v[i],pos.insert({-v[i],i});
  27.     for(i=n-1;i>0;i--){
  28.         p=*pos.begin();
  29.         if(p.first==(-v[i])){
  30.             p.second=i;
  31.             pos.erase(p);
  32.         }
  33.         else{
  34.             j=p.second;
  35.             pos.erase(p);
  36.             p.first=(-v[i]);p.second=i;
  37.             pos.erase(p);
  38.             swap(v[j],v[i]);
  39.             ans++;
  40.             pos.insert({-v[j],j});
  41.         }
  42.     }
  43.     cout<<ans;
  44.     cout<<"\n";
  45. }
  46.  
  47. int main()
  48. {
  49.     ios::sync_with_stdio(false);
  50.     cin.tie(nullptr);
  51.     int t=1;
  52.     while(t--)      run_case();
  53.     return 0;
  54. }
Success #stdin #stdout 0.01s 5392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/SjMvtC
language:
C++14 (gcc 8.3)
created:
1 year 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!