fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4. #define all(vec)  vec.begin(),vec.end()
  5. #define endl "\n"
  6. #define readall(n, arr) for(int i=0;i<(n);i++) cin>>arr[i]
  7. #define yes cout<<"YES\n"
  8. #define no cout<<"NO\n"
  9. #define loopi(n) for(int i=0;i<(n);i++)
  10. #define loopj(n) for(int j=0;j<(n);j++)
  11. #define loopk(n) for(int k=0;k<(n);k++)
  12. #define mods     (1000000007)
  13. #define float   double
  14. //#define N   100000+5
  15. using namespace std;
  16.  
  17. int binsrch(int arr[],int st,int nd,int k);
  18. int nCr(int n,int r);
  19. int nPr(int n,int r);
  20.  
  21. set<int>::iterator itr;
  22.  
  23. void solve(){
  24.     int n,counter=0;
  25.     cin>>n;
  26.     map<int,int> mp;
  27.     for(int i=0;i<n;i++) {
  28.         int x;
  29.         cin>>x;
  30.         mp[x]++;
  31.     }
  32.     map<int,int>::iterator it;
  33.  
  34.     for(it=mp.begin();it!=mp.end();it++) {
  35.         if((it->second)>1) {
  36.             counter+=(it->second)-1;
  37.             mp[(it->first)+1]+=(it->second)-1;
  38.             mp[(it->first)]-=(it->second)-1;
  39.         }
  40.     }
  41.     string s=to_string(counter);
  42.     cout<<s;
  43. }
  44.  
  45. int32_t main()
  46. {
  47.     ios_base::sync_with_stdio(false);
  48.     cout.tie(nullptr);
  49.     cin.tie(nullptr);
  50.     //freopen("input.txt", "r", stdin);
  51.     //freopen("output.txt","w",stdout);
  52.  
  53.     int t=1;
  54.     //cin>>t;
  55.  
  56.     while(t--){
  57.         solve();
  58.     }
  59.  
  60. }
  61.  
  62. int binsrch(int arr[],int st,int nd,int k){
  63.     int ans=0;
  64.     while(st<=nd) {
  65.         int md=(st+nd)/2;
  66.         if(k>=arr[md]) {
  67.             ans=md+1;
  68.             st=md+1;
  69.         }else {
  70.             nd=md-1;
  71.         }
  72.     }
  73.     return ans;
  74. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uufZwr
language:
C++ (gcc 8.3)
created:
9 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!